Cooley-Tukey FFT Algorithm

1

The classic Cooley-Tukey FFT was published in 1965. I’ve always wondered if an original implementation for the IBM computers exists in some archive. The paper can be downloaded here.

One of the earliest implementations of the algorithm (in ALGOL) is by Singleton, 1966-1967:

A Fortran version was published two years later, in 1969:

Transcriptions of Singleton’s Fortran program can be found in the Netlib “Golden Oldies” folder: go

Today I found a report dating back to 1967 from the MIT Lincoln Laboratory that contains Fortran source code:

Brenner, N. M. (1967). Three Fortran programs that perform the Cooley-Tukey Fourier transform. In Technical note / Lincoln Laboratory, Massachusetts Institute of Technology (1967,2). Lincoln Laboratory.

Edit: the homepage of author of the report: https://home.gwu.edu/~nbrenner/

8 Likes
2

Nice find! The code is unfortunately hard to read at some places:

image

But should be possible to “guess until it works”. It would be cool to get this 57 years old code working.

3

It was in the SIAM top ten algorithms of the 20th century and the original is not available in source form? A bit sad.

I might be wrong but I do not think they were the first to write it in FORTRAN though; I think that was Rudnick.

1 Like
4

John Burkardt, as usual, has it (subroutine realtr) in Fortran 90 in his version of the statistical data analysis library STARPAC.

5

Using an image editing program to increase the contrast and sharpen the image helps a little bit:

image

6

The report has errata sheets at the front clarifying some of the poorly reproduced code, including the section shown above

fft
fft861×572 61.7 KB

2 Likes
7

The following paper by Clive Temperton on his self-sorting in-place implementation of FFT contains a Fortran listing. Not the original algorithm but might actually be better for most applications (if you aren’t going to use FFTW).

https://www.sciencedirect.com/science/article/abs/pii/0021999185901640