ALGOL PROCEDURES FOR THE FAST FOURIER TRANSFORM

Abstract

The report consists of six ALGOL procedures with comments. Procedure FASTTRANSFORM computes the complex finite Fourier transform or its inverse, using a modified version of the fast Fourier transform algorithm proposed by Cooley and Tukey. Procedure REALTRANSFORM similarly computes the real Fourier transform and inverse. The remaining four procedures are building blocks used in the first two procedures: they may be combined in other ways, for example, to form procedures for computing convolutions and power spectral density function estimates. The fast Fourier transform is a significant advance over previous methods, in that the number of arithmetic operations is proportional to n log2 n instead of n(2). Detailed methods of computing this transform are shown here in the language of ALGOL. A new approach to organizing the computations is used, one that makes practical the solution of large problems in which data overlay within high speed storage will occur.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1966
Accession Number
AD0643996

Entities

People

  • Richard C. Singleton

Organizations

  • SRI International

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computers
  • Computing-Related Activities
  • Core Storage
  • Data Science
  • Data Storage Systems
  • Fast Fourier Transforms
  • Fourier Series
  • Identities
  • Operations Research
  • Permutations
  • Sequences
  • Statistics
  • Three Dimensional
  • Two Dimensional

Readers

  • Approximation Theory.
  • Computer Science.