Large number multiplication
noway at nohow.com
Wed Jul 6 22:15:06 CEST 2011
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.
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.
More information about the Python-list