BigInteger Tutorial
From a long time I was wondering what should be my next blog topic…..since in last few months I used lot of java.math.BigInteger class in most of my programs that’s why I have decided to write a small tutorial for it…. So here we go
You might be aware of the total storage capabilities of different data types which are used to store integer values in java … to brush up you can have a look at following grid (u can skip this section :) )
Java stores all integers in memory as binary numbers.
| type | Size | Range | |
| name | bytes | bits | |
| byte | 1 | 8 | -128 to +127 |
| short | 2 | 16 | -32768 to +32767 |
| int | 4 | 32 | -2147483648 to to +2147483647 |
| long | 8 | 64 | 9223372036854775808 to +9223372036854775807 |
[Source: http://leepoint.net/notes-java/data/basic_types/21integers.html]
There may be cases when we are interested in computation involving the numbers >264 so what data type should we use in that case. Java (I think 1.4.2 and higher) package comes with a BigInteger class which is designed to perform normal mathematical operation on 20-21 digit number or even high…..
Now in order to instantiate BigInteger class we can use any of the constructors specified in the following program
import java.math.BigInteger;
class Btest
{
public static void main(String args[])
{//1.BigInteger(byte[] val)
byte a[]={1,2,3,4};
BigInteger a1=new BigInteger(a);
System.out.println( a1);
/*2.BigInteger(int signum, byte[] magnitude) used to translate the sign magnitude of the BigInteger into BigInteger
signum - signum of the number (-1 for negative, 0 for zero, 1 for positive).
magnitude - big-endian binary representation of the magnitude of the number. */
BigInteger a2 = new BigInteger(1, a);
System.out.println( a2);
/*3.BigInteger(String val,int radix)
translates the String representation of BigInteger in the specified radix into a BigInteger
one can use optional minus "-"sign in the string parameter
*/
BigInteger a3 = new BigInteger("346433", 10);
System.out.println(a3);
/*4.BigInteger(String val)
translates decimal representation of a bigInteger specified in the string into corresponding BigInteger
*/
BigInteger a4=new BigInteger ("1231431543534");
System.out.println(a4);
/*5.BigInteger(int numBits,Random rnd)
this constructor generates a random BigInteger within interval [0,anitlog(numbits*log2)-1 ] */
java.util.Random r=new java.util.Random ();
BigInteger a5 = new BigInteger(32, r);
System.out.println(a5);
/*BigInteger(int bitLength,int certainty,Random rnd)
this constructor specifications leads to a randomely generated BigInteger which is probabaly prime.
Paramater bitlength specifies the bitlength of the desired BigInteger .
Parameter certainity specifies the certainity that could be tolerated by the caller
Parameter rnd is the source of random bits used to select candidates to be tested for primality.
*/
BigInteger a6 = new BigInteger(8, 56, r);
System.out.println(a6);
//Some other initialization techniques
BigInteger a6 = new BigInteger(8, 56, r);
System.out.println(a6);
BigInteger a7 = BigInteger.ONE;//can also use BigInteger.ZERO
System.out.println(a7);
BigInteger a8=BigInteger.valueOf(54353263);
System.out.println(a8);
}
}
OUTPUT
16909060
16909060
346433
1231431543534
94655163
191
1
54353263
Now we come to various methods which could be applied on BigInteger Objects. I have a written following program which involves most of the BigInteger methods however there a some more methods which are not given in program .You can get their detail here
import java.math.BigInteger;
class Btest1
{
public static void main(String args[])
/*--------------------------------Arithmetic and logical Methods--------------------------------*/
BigInteger x =BigInteger.valueOf(10);
BigInteger y = BigInteger.valueOf(8);
//add
x = x.add(BigInteger.valueOf(4));
x = x.add(y);
System.out.println(x);
//subtract
x = x.subtract(BigInteger.valueOf(4));
x = x.subtract(y);
System.out.println(x);
//divide
x = x.divide(BigInteger.valueOf(1));
x = x.divide(y);
System.out.println(x);
//multiply
x = x.multiply(BigInteger.valueOf(1));
x = x.multiply(y);
System.out.println(x);
//remainder
x = x.remainder(BigInteger.valueOf(4));
x = x.remainder(y);
System.out.println(x);
//divideAndRmainder
x = BigInteger.valueOf(43);
BigInteger s[] = new BigInteger[2];
s = x.divideAndRemainder(BigInteger.valueOf(5));
System.out.println("x/5="+s[0]+" "+"x%5="+s[1]);
s = x.divideAndRemainder(y);
System.out.println("x/y=" + s[0] + " " + "x%y=" + s[1]);
/*methods for Comparison */
//equals :returns true if parameter is equal to specified BigInteger
System.out.println (x.equals(BigInteger.valueOf(43)));
System.out.println (x.equals(y));
/*comapreTo :returns -1,0,1 depending on the value give as parameter is lesser than
,equal to,greater than the BigInteger for which the method is used */
System.out.println(x.compareTo(BigInteger.valueOf(42)));
System.out.println(x.compareTo(BigInteger.valueOf(43)));
System.out.println(x.compareTo(BigInteger.valueOf(44)));
//toString :used for String conversion
System.out.println(x.toString());
//to print corresponding byte,int,double,float,short value
System.out.println(x.byteValue());
System.out.println(x.doubleValue());
System.out.println(x.intValue());
System.out.println(x.floatValue());
System.out.println(x.shortValue());
byte x2[] = x.toByteArray();
for (int h=0;h
System.out.println(x2[h]);
/*isProbablePrime :returns true if the given BigInteger is prime ,
returns false if the given BigInteger is composite one has to menation integer value as the
parameter ,this integer value called "certainity" gives the measure of uncertainity which could be
tolerated */
System.out.println(x.isProbablePrime(23));
//pow :for raise to the power operation
System.out.println(x.pow(45));
//abs :used to return the absolute value
System.out.println(x.multiply(BigInteger.valueOf(-1)) + " " + x.multiply(BigInteger.valueOf(-1)).abs());
//negate returns -1*BigInteger
System.out.println(x.negate() + " " + x.multiply(BigInteger.valueOf(-1)).negate());
//hashCode:returns hashcode for the given BigInteger
System.out.println(x.hashCode());
//signm :Returns the signum function of the BigInteger.
System.out.println(x.signum());
/*------------------------------Bit Methods------------------------------*/
//shiftLeft
System.out.println(x.shiftLeft(4));
//shiftRight
System.out.println(x.shiftRight(4));
//bitCount returns the number of bits in two's complement notation apart frm the sign bit
System.out.println(x.bitCount());
//bitLength :returns the number of bits in minimal two's complement notation leaving the sign bit
System.out.println(x.bitLength());
//getLowestSetBit :returns the index of righmost one bit in the given BigInteger
System.out.println(x.getLowestSetBit());
//and
System.out.println(x.and(y));
//or
System.out.println(x.or(y));
//xor
System.out.println(x.xor(y));
//andNot
System.out.println(x.andNot(y));// returns x&~y
//not
System.out.println(x.not());
//testBit :returns true if designated bit is set
System.out.println(x.testBit(4));//test if ((x&(1<<4))!=0)>
/*setBit :returns a BigInteger which is generated by setting the specified bit of
the equivalent bit representation of Given BigInteger*/
System.out.println(x.setBit(4));// calculates x | (1<<4)
/*clearBit: returns a BigInteger which is generated by clearing the specified bit of
the equivalent bit representation of Given BigInteger*/
System.out.println(x.clearBit(4)); //calculates x&~(1<<4)
/*flipBit:returns a BigInteger which is generated by flipping the specified bit of
the equivalent bit representation of Given BigInteger*/
System.out.println(x.flipBit(4));//calculates x^~(1<<4)
}
}
OUTPUT
22
10
1
8
0
x/5=8 x%5=3
x/y=5 x%y=3
true
false
1
0
-1
43
43
43.0
43
43.0
43
43
true
32068636955638964644302091603013447460711607634633358021240791550942692443
-43 43
-43 43
43
1
688
2
4
6
0
8
43
35
35
-44
false
59
43
59
Till now you would be able to use the BigInteger class as per your needs .Following is a small code which I wrote to calculate the factorial of large values and store it in a text file generated at at C drive C:/fact.txt I have calculated the value of 40000!..which is incredibly huge …lol and uploaded the generated file here
import java.io.*;
import java.math.BigInteger;
class ffact
{
public static void main(String args[])throws Exception
{
BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
System.out.println("enter a value");
BigInteger a = new BigInteger(b.readLine());
BigInteger a1 = BigInteger.valueOf(1),a2=BigInteger.valueOf(1);
for (a1 = BigInteger.valueOf(1); a1.compareTo(a) <= 0; a1 = a1.add(BigInteger.valueOf(1)))
a2 = a2.multiply(a1);
File f2 = new File("c:/fact.txt");
if (!f2.exists()) f2.createNewFile();
PrintWriter p = new PrintWriter(new BufferedWriter(new FileWriter(f2.getAbsolutePath())));
p.println(a2);
p.close();
}
}
Anyways its 2:10 am … i guess I need some sleep now …hope I’ll come wid a new topic soon thinking to come up with internal working of BigInteger class next time Or I’ll come up wid some other topic …..
