Re: big number arithmetic

Thus spake John Nietzsche ([email protected]):
> I would like to go for karatsuba at a first try. I have implemented a
> code to multiple two 64 bit number on intel P4 machine. Here it is.

> (a0 + a1 * 2 ^ 32) * ( b0 + b1 * 2 ^ 32) = a0b0 + (a0b0 + a1b1 + (a0 -
> a1)*(b1 - b0)) * 2 ^ 32 + a1b1 * 2 ^ 64.

Don't.  Karatsuba starts to be useful (depending on the architecture) at
1024 bit numbers and up.  Do the school method for smaller numbers, as
someone else already suggested.

BTW: on 64-bit platforms you usually already have 64x64->128
multiplication as instruction.  gcc even has an int128_t type for this.

Felix