Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] abua_v1_0.gz(11 Kbytes)
Manuscript Title: FOUR67, a fast Fourier transform package.
Authors: J.P. Christiansen, R.W. Hockney
Program title: FOUR67
Catalogue identifier: ABUA_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 2(1971)127
Programming language: Fortran.
Computer: ICL KDF9.
Operating system: EGDON 3.
RAM: 3K words
Word size: 48
Keywords: General purpose, Fourier, Time series analysis, Analysis, Synthesis, Sine analysis, Cosine analysis, Harmonic, M.h.d, Fast fourier transform.
Classification: 4.6.

Nature of problem:
FOUR67 performs a finite Fourier analysis or synthesis on a given vector. It can carry out sine analysis or synthesis for odd functions, cosine analysis or synthesis for even functions, and sine and cosine analysis or synthesis for periodic functions.

Solution method:
It is known that the harmonics in a finite Fourier expansion of a function u(x) can be computed exactly from a discrete set of equidistantly spaced values u(Delta x), u(2Delta x), u(3Delta x).... To minimize the number of arithmetic operators involved, FOUR67 employs a two-folding method before multiplication with the sine and cosine terms. The two-folding method, which takes advantage of the symmetry of sine and cosine functions, implies additions only and is therefore well- suited to fast numerical computations.

Restrictions:
FOUR67 will perform a finite Fourier analysis or synthesis (of any of the three types mentioned above), on any real vector with a dimension N = 2IQ + 1. The calculation is done in floating point form, the integer IQ is limited to 3 at the lower end by the logic, and at the upper end only by limitations of storage.

Unusual features:
The program is written in ASA FORTRAN apart from the use of symbolic dimensions, which on certain computer systems must be replaced by actual numerical values. The PRELUDE section should then be removed. When used repeatedly this package should be programmed in assembly code to achieve maximum speed, and FOUR67 has been designed with this end in mind.

Running time:
The execution times depend on N as well as on the type of analysis or synthesis. On the ICL KDF9 a vector length 64+1 takes approximately 0.2 s to analyse or synthesise.