How do BigNums implementations work?

Question

I wanted to know how the BigInt and other such stuff are implemented. I tried to check out JAVA source code, but it was all Greek and Latin to me. Can you please explain me the algo in words - no code, so that i understand what i am actually using when i use something from the JAVA API. regards

Answer 1

Conceptually, the same way you do arbitrary size arithmentic by hand. You have something like an array of values, and algorithms for the various operations that work on the array.

Say you want to add 100 to 901. You start with the two numbers as arrays:

 [0, 1, 0, 0]
 [0, 9, 0, 1]

When you add, your addition algorithm starts from the right, takes 0+1, giving 1, 0+0, giving 0, and -- now the tricky part -- 9+1 gives 10, but now we need to carry, so we add 1 to the next column over, and put (9+1)%10 into the third column.

When your numbers grow big enough -- greater than 9999 in this example -- then you have to allocate more space somehow.

This is, of course, somewhat simplified if you store the numbers in reverse order.

Real implementations use full words, so the modulus is really some large power of two, but the concept is the same.

There's a very good section on this in Knuth.