The FFT: an algorithm the whole family can use

2000/01/01 by Daniel N. Rockmore · 3 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Computability, Logic, AI Algorithms #Quantum-Dot Cellular Automata

paper · doi:10.1109/5992.814659

openalex publication_date 2000/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/04

Abstract

The fast Fourier transform is one of the fundamental algorithm families in digital information processing. The author discusses its past, present, and future, along with its important role in our current digital revolution. It is concluded that the FFT is both parent and child of the digital revolution, a computational technique at the nexus of the worlds of business and entertainment, national security and public communication. Although it is anyone's guess as to what lies over the next horizon in digital signal processing, the FFT will most likely be in the thick of it.

Citations

• An algorithm for the machine calculation of complex Fourier series
• Fast Fourier Transforms
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited by

• Generating and Searching Families of FFT Algorithms
• The Nature of Computation
• Fast Fourier transform [wikipedia]