Large number multiplication

[Christian Heimes]

Am 06.07.2011 22:15, schrieb Billy Mays:
> 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.

It might work for medium large longs but how about really large longs
like 5 * 1,000**10,000? I'm not familiar with FFT based multiplication
but I guess that very large numbers are going to introduce rounding
errors if floating points are involved.

Python used to run on platforms without an FPU and floats. These days
Python might still run on platforms with just an emulated FPU. Unless
there is a way to implement FFT without floating point ops, an emulated
or missing FPU makes FFT slower than Karatsuba. There might be one but I
haven't learned a way in my numerics classes.

Christian