Steinar, thanks for the pointer...some of that paper's citations were interesting also. General note, the analysis therein is only an RMS error measure, not of phase errors, but does include convolution error in addition to DFT error.
The problem I am trying to sort through relates to computation of cos(PI/2^n) when sin(PI/2^n) ~ representation_epsilon; Perhaps GW should comment on the accuracy of Prime95 convolution. Last time that I looked it was using transforms 2^21 and 2^22 in length for exponents up to 33,554,432; on a 16-bit representation stored in a [sign]+23-bit mantissa single-precision float. For all intents and purposes with 16-bit numerical precision, FP32_cos(PI/2^n) == ONE, for n>=10. This suggests a speedup optimization for Prime95 and any other DFT > 2^10 in single-precision ... just use ONE instead of FP32_cos for the twiddle factor for stages 10 to last, eliminating approximately 1/3 FLOPS on those stages, and actually allows each complex multiply to complete with 2 fused MADD, or 2 complex multiply per SSE SIMD-FP32 operation on a Core2 Intel. Quote from the Schatzman paper: "(5) The computation of long DFTs with IEEE 32-bit floating point is a process about which one should be cautious. If accuracy of better than 0.1% is required (three digits) for transforms in the 10,000+ point range, 64-bit floating point or a very carefully implemented 32-bit FFT should be used." food for thought? -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Steinar H. Gunderson Sent: Sunday, February 03, 2008 9:58 AM To: [email protected] Subject: Re: [Prime] twiddle factor computation error: cos(PI / (2^n)) On Sun, Feb 03, 2008 at 09:33:55AM -0800, Paul Charlton wrote: > Can anyone point to cogent analysis of the representational error in twiddle > factors due to cos(PI / 2^N) ? The only paper I've seen regarding twiddle factor accuracy's influence on the FFT is James C. Schatzman. Accuracy of the discrete Fourier transform and the fast Fourier transform. SIAM Journal on Scientific Computing, 17(5):1150–1166, 1996. IIRC it's a bit hard to find online, though, and it was mostly experimental. /* Steinar */ -- Homepage: http://www.sesse.net/ _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
