At Tue, 10 Sep 2002 15:33:17 EDT, [EMAIL PROTECTED] wrote: >In that sense, floating-point FFT and NTT are similar - >in both cases you need enough bits to accomodate the full convolution >output digits. The only advantage NTT has here is that you don't sacrifice >any bits of your computer words to roundoff error, nor to the exponent field >floats are required to carry around.
With regard to performing FFTs using approximate arithmetic, it's worth noting that floating-point arithmetic results in an asymptotically better worst case error (O(n log n)) than any fixed point arithmetic (O(n^2)). Colin Percival _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
