Report Number: CS-TR-65-32
Institution: Stanford University, Department of Computer Science
Title: Minimum multiplication Fourier analysis
Author: Hockney, Roger W.
Date: December 1965
Abstract: Fourier analysis and synthesis is a frequently used tool in
applied mathematics but is found to be a time consuming
process to apply on a digital computer and this fact may
prevent the practical application of the technique. This
paper describes an algorithm which uses the symmetries of the
sine and cosine functions to reduce the number of arithmetic
operations by a factor between 10 and 30. The algorithm is
applicable to a finite fourier (or harmonic) analysis on $12
\bigotimes\ 2^q$ values, where q is any integer $\geq$ 0 and
is applicable to a variety of end conditions. A complete and
tested B5000 Algol program known as FOURIER12 is included.