mersenneforum.org > Math Van Buskirk/DJB's Tangent FFT
 Register FAQ Search Today's Posts Mark Forums Read

2007-08-29, 11:20   #1
akruppa

"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Van Buskirk/DJB's Tangent FFT

Quote:
 Date: 12 Aug 2007 16:55:34 -0000 Mail-Followup-To: bnis@list.cr.yp.to Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html. From: "D. J. Bernstein" To: bnis@list.cr.yp.to Subject: The tangent FFT Content-Disposition: inline If you're using the complex-floating-point split-radix FFT, you can gain a constant factor in total floating-point operations (asymptotically more than 5%!) by switching to the tangent FFT: http://cr.yp.to/papers.html#tangentfft The operation count is due to Van Buskirk. The algorithm in my paper has the virtue of being simultaneously simple, in-place, and cache-friendly. I haven't seen a serious analysis of the impact of Van Buskirk's ideas for cost measures more complicated than counting arithmetic operations. The Johnson-Frigo paper on the topic claims that practical performance of FFTs is "unpredictable"; I see no justification for this claim, and my own FFT optimization experience tells me that the opposite is true. Has anyone tried a serious implementation of Van Buskirk's FFT? - ---D. J. Bernstein, Professor, Mathematics, Statistics, and Computer Science, University of Illinois at Chicago
Could this be of interest for Prime95? (Note: I have not read the paper yet.)

Alex

 2007-08-29, 21:24 #2 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×599 Posts ~5.5 percent speedup in every single Lucas-Lehmering, P-1ing, ECMing, cotton-picking FFT, and Bernstein's way of explaining makes me think of finally (41 years after first wondering what "Cooley-Tukey" on all those other printouts meant) plunging in to learn how FFT works! Last fiddled with by cheesehead on 2007-08-29 at 21:42 Reason: reminiscing about the summer of '66