Large number multiplication

[Christian Heimes]

Am 06.07.2011 21:30, schrieb Billy Mays:
> I was looking through the python source and noticed that long 
> multiplication is done using the Karatsuba method (O(~n^1.5)) rather 
> than using FFTs O(~n log n).  I was wondering if there was a reason the 
> Karatsuba method was chosen over the FFT convolution method?

The Karatsuba algorithm uses just addition, subtraction and
multiplication, so you don't need to resort to floats and have no
rounding errors. On the other hand FFT are based on e, complex numbers
or trigonometric functions (=floats), which mean you'll get rounding errors.

We don't want rounding errors for large long multiplication.

Christian