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 -- http://mail.python.org/mailman/listinfo/python-list
