Large number multiplication

Christian Heimes lists at cheimes.de
Wed Jul 6 22:05:52 CEST 2011


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




More information about the Python-list mailing list