Thread: HugeInt (BigInt) optimization

A few of you have mentioned in the "Division Algorithm" thread that you've your own BigInt type classes. I'd just like to know two things:
1) How you store your data and what kind of data it is
2) The speed of performing large calculations (examples: factorial 1200, for i = 0 to 1000 2^i)
If it's too inconvenient you don't have to go out of your way to determine actual time in seconds (but if you could it would help); a relative estimate would do.

I'm curious because I've been working on a HugeFloat class that has been working very well. I started thinking about starting from scratch because the code for most functions is very long and complex and I've been doing some reading and thought perhaps storing the data with a large base might yield simpler algorithms yet maintain fast speeds. I just wrote a simple class storing data using base 65536 and it performs horribly. My HugeFloat class can perform factorial 1200 in under a second and print out from i = 0 to 1000, 2^i in about 8 seconds, but the new class cannot even calculate 2^8 within several minutes (that's when I killed it).

Your thoughts?

Powers of integers can be optimized heavily.

Example:

Code:

x^276  =  x^100010100b = x^256 * x^16 *x^4  = 

= (..(x^2)^2)^2)^2)^2)^2)^2) * (..(x^2)^2)^2)^2) * (x^2)^2

This improves performance a lot. Only 14 multiplications are done when raising x to the power of 2.

And if you use binary internal representation, powers of two can be calculated in constant time.

2^n = 1000...00 (n zeroes)