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 .

Implementations

  • FFTPACK -- Fourier Transform Library (C) (rating 10)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 6)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 4)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 3)
  • Algorithms in C++ -- Sedgewick (C++) (rating 2)

    Related Problems

  • Arbitrary Precision Arithmetic
  • Simplifying Polygons
  • Text Compression

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .