On Thu, 17 Jun 1999, Blosser, Jeremy wrote:
> See: http://www.hut.fi/~mtommila/ntt.html for a decent explanation of an NTT
> and how it relates to FFTs. At some point GIMPS would either have to move to
> quad precision primes or an NTT algorithm because of round-off errors (not
> enough bits... I think it'll die around 32-bit? And right now we're at 19 or
> something?)
With the discrete weighted transforms GIMPS uses now, you can simply
perform a larger FFT and keep the number of bits per double the same.
> DWT is the discrete walsh transform... of which there is of course the FWHT
> (Fast Walsh-Hadamard Tranform). Which is considered a "poor man's FFT" a lot
> of the time. Its faster than an FFT, but I think the issue is that there is
> no real way to do a convolution via FWHT (that has been found yet?)
Richard Crandall's book "Topics in Advanced Scientific Computation" has a
way to do convolutions via fast Walsh transforms, but it's somewhat
complicated and for large sizes the FFT is still faster (at least from an
operation count point of view)
jasonp
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
