-   Math (
-   -   Van Buskirk/DJB's Tangent FFT (

akruppa 2007-08-29 11:20

Van Buskirk/DJB's Tangent FFT
Date: 12 Aug 2007 16:55:34 -0000
Mail-Followup-To: [email][/email]
Automatic-Legal-Notices: See [url][/url].
From: "D. J. Bernstein" <>
To: [email][/email]
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:


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.)


cheesehead 2007-08-29 21:24

~5.5 percent speedup in every single Lucas-Lehmering, P-1ing, ECMing, cotton-picking FFT, [I]and[/I] 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!

All times are UTC. The time now is 10:57.

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