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