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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/65/32/CS-TR-65-32.pdf