Large number multiplication

[Billy Mays]

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