On Sun, 16 Jul 2000, Dave Mullen wrote:
> I think the next true breakthrough on LL testing will only come when
> someone finds how to do an FFT or other transform without the need to
> "spread" the 2^N-1 values into a 2^N FFT space (my terminology might
> be bad, I hope you know what I mean) - and avoid the floating point
> inaccuracies (and the subsequent required error checking) - anyone
> done any more reseach on the NTT or similar integer transforms ?
Already being used in mprime/prime95, with Crandall's algorithm the
convolution is tightly packed and the modulus is given for free.
Also, a floating point algorithm is used because modern processors does
more bits accurately in the same time with floats than with integers, even
if you have to throw some bits away with floats.
As a result integer algorithms are slower on current hardware, so is used
mainly to validate the floating point algorithm implemementations.
> I did have a "play" with NTTs, in an attempt to try and do more that
> one iteration per forward and reverse transform, but found the
> difficulty is finding a big enough prime with suitable roots to cope
> with the magnitude of numbers ^2, never mind ^4 !
>
> Dave
--
Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/
Linux isn't at war. War involves large numbers of people making losing
decisions that harm each other in a vain attempt to lose last.
Linux is about winning. Alan Cox on linux-kernel
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
