Java BigInteger's

[Gox]

Hi,

I've written a little program to calculate Fibonacci numbers up to F(300). If you have knowledge of Fibonacci, you'll know that the number get very large, very quickly.
i.e F(300) =222232244629420445529739893461909967206666939096499764990979600

Obviously this number can't be stored in an Int or Long etc. To solve the issue I've used Java's BigInteger Class to store these numbers. It works well. However, I would like to understand how BigInteger works "under the hood". Does it store the numbers as byte arrays, as Strings etc?

Java's API for BigInteger doesn't seem to specify how it works in terms of how it stores numbers, just how to use the class. If anyone can explain, or point me in the direction of a write up on how BigInteger stores it's numbers that would be quite helpful.

Thanks,
Gox

[Aradon]

Hm, a good question.

I'm unsure to be honest and someone with a sun certification may be able to tell you. (if not here on sun's site). I did find this information:


You can handle a number with as many digits as you have RAM.

Which makes me think that perhaps what they do is they create an array where each array element corresponds to a digit. That way you're not limited on size, per say. And with the many copy algorithms out there for increasing array size I wouldn't be surprised.

However this is only a guess.

Edit*
I found the GNU Open Source BigInteger implementation which I would guess just about mimics it.

GNU BigInteger (http://developer.classpath.org/doc/java/math/BigInteger-source.html)

[Gox]

Aradon, thanks for your reply and information.

I'll continue to do some more sleuthing.

EDIT: Based on the following, my guess is the number is stored as an array of ints (i.e words). Can anyone comment on whether they agree or disagree with this assumption?

/** All integers are stored in 2's-complement form.
63: * If words == null, the ival is the value of this BigInteger.
64: * Otherwise, the first ival elements of words make the value
65: * of this BigInteger, stored in little-endian order, 2's-complement form. */
66: private transient int ival;
67: private transient int[] words;

This appears to be what Aradon suggested. An int array, where each spot in the array holds a digit of the number.

Gox