On 07/06/2011 04:05 PM, Christian Heimes wrote:
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
I believe it is possible to do FFTs without significant rounding error.
I know that the GIMPS's Prime95 does very large multiplications using
FFTs (I don't know if they use the integer based or double based
version). I also know they have guards to prevent rounding errors so I
don't think it would be impossible to implement.
--
Bill
--
http://mail.python.org/mailman/listinfo/python-list
