On Tuesday 04 March 2008 16:06, Brian Beesley wrote: > On Tuesday 04 March 2008 08:52, Daran wrote: > > A test which requires only squarings could be done entirely in Fourier > > space, with just one transform at the beginning, and an inverse one at > > the end. > > > > Or am I missing something? Error correction and rounding perhaps? > > Yup. We get ~ 20 bits precision from a 53 bit manitissa for one squaring. > Even if you only did 2 squarings between inverse transforms you'd never get > the right output.
We can't round in FT space because we use an floating point FFT. But http://mersenne.org/math.htm says "Although GIMPS uses a floating point FFT for reasons specific to the Intel Pentium architecture, Peter Montgomery showed that an all-integer weighted transform can also be used." My first thought is that with modern PCs working with 64 bit integers why can't we get 32 bits precision using them anyway? But even if FP arithmetic does give more precision, by implementing an integer transform, the rounding could be done within FT space. I could still be missing something. Isn't there a separate 'carry' step to an FFT multiplication which needs to be done every time, outside FT space, even if there was no need to round? > Regards > Brian Beesley Daran _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
