 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
[Tutorial] BigInteger's, Handle Very Large Numbers!        Author Message
the_short1  Posted: Mon Jul 24, 2006 11:36 pm   Post subject: [Tutorial] BigInteger's, Handle Very Large Numbers!

BigIntegers, What Are They?

(From sun.com) "Immutable arbitrary-precision integers."
(From Answers.com) Immutatble: "Incapable of changing or being modified", meaning the precision cannot be changed (any one else have a better.. desc?)

In 'Laymans' terms, they are very large 'integer' type variables, with the capacity to hold as many digits as your RAM will fit.

When Should You Use Them?

They should be used whenever you need to handle very large numbers, anything larger then 'long' variables. Long's have a max a max value of 9223372036854775807. As well, BigInteger provides some useful functions for bit manipulation, GCD, random number, and primality testing and generation.

Do I Need To Import Anything?

Yes, add this import line at the top of your java file
 Java: import java.math.*;

Declaring A BigInteger Variable (4 Examples)

 Java: BigInteger bigInt0 = BigInteger.ZERO; BigInteger bigInt1 = BigInteger.ONE; BigInteger bigInt3 = new BigInteger ("3"); BigInteger bigInt5 = BigInteger.valueOf(5);

Note: You cannot pass an int/long into a BigInteger directly, the easiest way to do this it to pass it as a static BigInteger using valueOf, Thank You "OneOffDriveByPoster" for that method.

 Java: long num = 9876543210; BigInteger bigInt123 = BigInteger.valueOf (num);

So, How Do I Use Them?

Well, BigIntegers contain all the regular math functions, plus more, the main difference is, it does not use symbols such as '*', '+','=','>' etc. rather it uses words (multiply,add,equals,compareTo). Examples;

To Multiply:
 Java: bigInt1.multiply(bigInt3);

Returns: A Big Integer With Value 3 (1*3)
Whereas, bigInt1 and bigInt3 are both BigInteger's

To Subtract:
 Java: bigInt1.subtract(bigInt3);

Returns: A BigInteger with value -2 (3-1)
Whereas, bigInt1 and bigInt3 are both BigInteger's

To Compare:
 Java: bigInt1.compareTo(bigInt3);

Returns: An Integer with a value of -1 (Less Than), 0 (Equal), 1 (Greater Then), in this case, it will be -1 since 1 is less then 3.
Whereas, bigInt1 and bigInt3 are both BigInteger's

To Check If Equal:
 Java: bigInt1.equals(bigInt3);

Returns: A boolean with a value of false since 1 != 3
Whereas, bigInt1 and bigInt3 are both BigInteger's

Youll notice, its just like dealing with strings (equals, compareTo)...

As well, you can create a new BigInteger inline (outputs 8)
 Java: System.out.println ("2**3 = "+new BigInteger("2").pow(3));

Note: I Used this as a special example, 'pow', raises the BigInteger '2' to the power of a regular integer '3'. Most of the math methods need BigIntegers as the initial and secondary values but this is a worthy exception to point out.

Can I Make An Array?

Sure, why not, arrays can be made of any object/class. Both arrays have a length of 10, both have been initiallized to value '1'
 Java: //------Example One-------// BigInteger i = BigInteger.ONE; BigInteger [] biggg = {i,i,i,i,i,i,i,i,i,i}; //------Example Two-------// BigInteger [] biggg = new BigInteger ; for (int c = 0; c < biggg.length; c ++){     biggg [c] = BigInteger.ONE; }

You Mentioned Primality Testing...

Checking if a number is prime is easy with BigIntegers,
 Java: if (new BigInteger("17").isProbablePrime(5) == true){         System.out.println("17 Is Prime!"); }

Note: The 5 is the certainty that the number is prime, this value reflects how long it takes to complete, for small primes, a value of 1-5 works, but bigger numbers may return false positives unless certainty is >= 5.

Im A 'Bit' Hungry, Lets Do Bit Manipulation!

One of the most used is XOR, in encryption methods. Eg: 65 XOR 42 = 107, and 107 XOR 42 = 65. The work behind this is, it converts the numbers to binary (1's, 0's), and compares the bits in each position, if they are different, bit = 1, if they are the same, bit = 0
Kevin wrote:

65: 1000001_______107: 1101011
XOR______________XOR
42: 0101010_______42: 0101010
=________________=
107: 1101011______65: 1000001

 Java: System.out.println ("65 XOR 42 = "+new BigInteger("65").XOR(new BigInteger("42"));

Constant Recomendations

Seeing how it takes quite a bit of typing to make a new biginteger every time you say want to multiply something by two... bigInt.multiply (new BigInteger("2");.. etc.. I recomend making some constants at the top of your program for the most common numbers as follows:

 Java: BigInteger TWO = new BigInteger ("2"); BigInteger THREE = new BigInteger ("3"); BigInteger FIVE = new BigInteger ("5"); BigInteger TEN = new BigInteger ("10"); ... System.out.println ("2 * 10 = "+TWO.multiply(TEN));

What About For Loops, Can BigIntegers Be Used?[b]

They can be, but its unadvisable as it will be extremly slow, unless incrementing by say 100 or 1000... (bellow i used 1 for increment)...

 Java: for (BigInteger bigCount = BigInteger.ZERO; bigCount.compareTo(new BigInteger ("99999999999999999")) == -1; bigCount = bigCount.add(BigInteger.ONE)){      System.out.println ("Big:"+bigCount); }

[b]Can I See A Full Program Using BigIntegers?

Sure...A Method To Evaluate Factorials! I used BigInteger for the result, because even 25! uses 26 digits, far larger then the max 'long' capacity.

 Java: public static BigInteger factorial(int n){     /* n must be >= 0, 0! = 1, eg: n=5 returns (5x4x3x2x1) */     /* Holds the value of the factorial, in BigInteger form */     BigInteger product = BigInteger.ONE;             /* Inform User that n was erroneous parameter */     if (n < 0){         System.out.println ("Factorial Error! n = "+n);         return new BigInteger ("-1");     }                /* Chain Multiply from 'n' to '1' */     for (int c = n; c > 0; c --){         product = product.multiply(BigInteger.valueOf(c));     }                             System.out.println ("Factorial "+n+"! = "+product);             /* Return a BigInteger with the product from n! */     return product; }// end factorial

Check Out Sun's Java Docs On BigInteger. BigInteger @ Sun.com
(I Highly Recoment You Read Through The Whole Method Summary Section)

As well, for the decimal equivalent, check out 'BigDecimal' BigDecimal @ Sun.com
BigDecimal's use the same concepts as BigInteger, so i wont go into much detail, but if you have questions about BigDecimals, ask away.    OneOffDriveByPoster Posted: Tue Jul 25, 2006 8:07 am   Post subject: Re: [Tutorial] BigInteger's, Handle Very Large Numbers!

the_short1 wrote:
Note: You cannot pass an int/long into a BigInteger directly, the easiest way to do this it to pass it as a new BigInteger in string format.

 Java: int num = "123"; BigInteger bigInt123 = new BigInteger (""+num);

Or...
 Java: BigInteger.valueOf(123);

Using static methods in this way is a common pattern. the_short1  Posted: Tue Jul 25, 2006 10:38 am   Post subject: Re: [Tutorial] BigInteger's, Handle Very Large Numbers!

OneOffDriveByPoster wrote:
the_short1 wrote:

 Java: int num = "123"; BigInteger bigInt123 = new BigInteger (""+num);

Or...
 Java: BigInteger.valueOf(123);

Using static methods in this way is a common pattern.

Thank you, i will make the change to reflect that. They ought to have a contructor for that, instead of having it listed at the very bottom as valueOf. And you inadvertantly discovered a typo, i had 123 wrapped in quotes..lol... guess it was kinda late when i posted that (12:30). cool dude  Posted: Tue Jul 25, 2006 11:02 am   Post subject: (No subject)

thanks for the tutorial. i was hoping someone would make it on BigInteger. would you be able to use BigInteger in a for loop if the number you want to go up to is really large? the_short1  Posted: Tue Jul 25, 2006 8:04 pm   Post subject: (No subject)

cool dude wrote:
thanks for the tutorial. i was hoping someone would make it on BigInteger. would you be able to use BigInteger in a for loop if the number you want to go up to is really large?

Thank you, i just realized i forgot comparison operators.. I aught to mention they are words too..

Anyways, certainly you can use BigIntegers in a for loop, they are just another number 'type'.

This for loop starts at zero, and increments by 1, providing that bigCount is less then 99999999999999999

 Java: for (BigInteger bigCount = BigInteger.ZERO; bigCount.compareTo(new BigInteger ("99999999999999999")) == -1; bigCount = bigCount.add(BigInteger.ONE)){      System.out.println ("Big:"+bigCount); } [Gandalf]  Posted: Tue Jul 25, 2006 8:53 pm   Post subject: (No subject)

You can replace:
 code: bigCount.compareTo(new BigInteger ("99999999999999999")) == -1;

With:
 code: !bigCount.equals(new BigInteger ("99999999999999999"));  the_short1  Posted: Wed Jul 26, 2006 9:54 am   Post subject: (No subject)

[Gandalf] wrote:
You can replace:
 code: bigCount.compareTo(new BigInteger ("99999999999999999")) == -1;

With:
 code: !bigCount.equals(new BigInteger ("99999999999999999")); Guess i could, but thats not the point, i was purposely demontrating the '<' operator (-1)... Java is a huge language, and there is soo much to learn it is imposible to know it all, the !"123".equals("1234") trick i did not know, but i see how its no diff then != true, since true is the asummed boolean when not mentioned. Thx. cool dude  Posted: Wed Jul 26, 2006 10:18 am   Post subject: (No subject)

thanks. another question, how would you use BigInteger as an array. the way i though which doesn't work is like so:

 code: BigInteger[] arry = new BigInteger; arry.equals(1);    wtd Posted: Wed Jul 26, 2006 11:12 am   Post subject: (No subject)

Your question goes to how Object types are handled in arrays.

When an array of Objects is created with "new", the individual objects in that array are not initialized. cool dude  Posted: Wed Jul 26, 2006 11:27 am   Post subject: (No subject)

wtd wrote:
Your question goes to how Object types are handled in arrays.

When an array of Objects is created with "new", the individual objects in that array are not initialized.

yes, now the question is how can i individually initialize them. as you can tell
 code: arry.equals(1);
does not work wtd Posted: Wed Jul 26, 2006 11:42 am   Post subject: (No subject)

How would you initialize the following?

 code: BigInteger i; cool dude  Posted: Wed Jul 26, 2006 1:13 pm   Post subject: (No subject)

thanks code: i = BigInteger.valueOf(3); [Gandalf]  Posted: Wed Jul 26, 2006 4:04 pm   Post subject: (No subject)

the_short1 wrote:
...i was purposely demontrating the '<' operator (-1)...

I know, but it's good to know both methods. The alternative is less code, and IMO much more expressive.

the_short1 wrote:
...the !"123".equals("1234") trick i did not know, but i see how its no diff then != true, since true is the asummed boolean when not mentioned.

Again, it's less code, and I think more expressive...
"123" is not equal to "1234" as opposed to "123" is equal to "1234" is not true. OneOffDriveByPoster Posted: Wed Jul 26, 2006 10:03 pm   Post subject: (No subject)

[Gandalf] wrote:
You can replace:
 code: bigCount.compareTo(new BigInteger ("99999999999999999")) == -1;

With:
 code: !bigCount.equals(new BigInteger ("99999999999999999"));

:)

I would prefer
 Java: bigCount.compareTo(new BigInteger ("99999999999999999")) < 0;

I believe it extends to other contexts and relational operators in a more general manner. the_short1  Posted: Wed Jul 26, 2006 11:21 pm   Post subject: (No subject)

OneOffDriveByPoster wrote:
[Gandalf] wrote:
You can replace:
 code: bigCount.compareTo(new BigInteger ("99999999999999999")) == -1;

With:
 code: !bigCount.equals(new BigInteger ("99999999999999999")); I would prefer
 Java: bigCount.compareTo(new BigInteger ("99999999999999999")) < 0;

I believe it extends to other contexts and relational operators in a more general manner.

@OneOff, I guess thers many ways to skin a cat, which one is most efficent? Not always that evident... Which one is most user-friendly? Depends on the person... @ Gandalf, yes it is less code, but sometimes its easy to miss the '!' in front when reading through the code thats not exactly fresh in your head (not trying to argue, just noting a point to others), i have started to use the ! in a few cases.

@Cool Dude, i added array initialization to the tutorial... (i dont see how what WTD wrote turned into what you wrote) Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Page 1 of 2  [ 17 Posts ]
Goto page 1, 2  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: