mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-08-29, 11:20   #1
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default 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" <djb@cr.yp.to>
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
akruppa is offline   Reply With Quote
Old 2007-08-29, 21:24   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

~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
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Tangent and the golden mean mfgoode Puzzles 1 2007-01-31 16:26

All times are UTC. The time now is 07:20.

Tue Nov 24 07:20:38 UTC 2020 up 75 days, 4:31, 4 users, load averages: 1.74, 1.53, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.