Proceedings of the National Academy of Sciences · 1976 · 251 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsTheory Of ComputationDigital Signal ProcessingFourier AnalysisNumber-theoretic AlgorithmsNumerical AlgorithmsNumerical AnalysisSignal ProcessingData Processing AlgorithmsDiscrete Fourier TransformFourier Transform
New algorithms for computing the Discrete Fourier Transform of n points are described. For n in the range of a few tens to a few thousands these algorithms use substantially fewer multiplications than the best algorithm previously known, and about the same number of additions.