Go Back > Great Internet Mersenne Prime Search > Math

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

2,467 Posts
Default Van Buskirk/DJB's Tangent FFT

Date: 12 Aug 2007 16:55:34 -0000
Automatic-Legal-Notices: See
From: "D. J. Bernstein" <>
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.)

akruppa is offline   Reply With Quote
Old 2007-08-29, 21:24   #2
cheesehead's Avatar
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 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
cheesehead is offline   Reply With Quote

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 00:13.

Tue Nov 30 00:13:23 UTC 2021 up 129 days, 18:42, 0 users, load averages: 1.06, 1.14, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.