The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.2.11 Discrete Fourier Transform

Problem Input | Problem Output

INPUT                    OUTPUT

Input Description: A sequence of n real or complex values h_i, 0 \leq i \leq n-1, sampled at uniform intervals from a function h.

Problem: The discrete Fourier transform H of h, H_m = \sum_{k=0}^{n-1} h_k e^{2 \pi i k m / n}, 0 \leq m \leq n-1.

Excerpt from The Algorithm Design Manual: Although computer scientists tend to be relatively unfamiliar with Fourier transforms, electrical engineers and signal processors eat them for breakfast. Functionally, Fourier transforms provide a way to convert samples of a standard time-series into the ``frequency domain''. This provides a ``dual'' representation of the function, in which certain operations become easier than in the time domain. Applications of Fourier transforms include:


  • FFTPACK -- Fourier Transform Library (C,FORTRAN) (rating 10)
  • Fastest Fourier Transform in the West (C) (rating 10)
  • GSL - GNU Scientific Library (C++,C) (rating 9)
  • FFT - Fast Fourier Transform (C,FORTRAN) (rating 7)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)

  • Recommended Books

    Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky A Primer on Wavelets and Their Scientific Applications by J. Walker The Fourier Transform and its Applications by R. Bracewell
    Numerical Recipes in C by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery The Fast Fourier Transform and Its Applications by E. Oran Brigham

    Related Problems

    Arbitrary Precision Arithmetic
    Simplifying Polygons
    Text Compression

    This page last modified on 2008-07-10 .