Using the circular convolution algorithms
described above, we can easily design algorithms
for prime length FFTs.
The only modifications that needs to be made involve
the permutation of Rader [5] and
the correct calculation of the DC term (

In the version we have currently implemented
and verified for correctness,
we precompute the multiplicative constants, the input permutation and the
output permutation.
From Equation 8 from A Bilinear Form for the DFT, the multiplicative constants are given
by

In an in-place in-order prime factor algorithm for the DFT [1], [6],
the necessary permuted forms of the DFT can be obtained
by modifying the multiplicative constants.
This can be easily done by permuting the roots of unity,

**Operation Counts**

Table 1 lists the arithmetic operations
incurred by the FFT programs we have generated and
verified for correctness.
Note that the number of additions and multiplications
incurred by the programs we have generated
are the same as previously existing programs for prime lengths
up to and including 13.
For

There are several table of operation counts in [4], each table corresponding to a different variation of the algorithms used in that paper. For each variation, the algorithms we have described use fewer additions and fewer multiplications. The focus of [4], however, is the implementation of prime point FFT on various computer architectures and the advantage that can be gained from matching algorithms with architectures. It should be noted that the highest prime in [4] for which an FFT was designed is 29. Although we have not executed the programs described in this paper on these computers, they are, as mentioned above, written to be easily adapted to parallel/vector computers.

P | muls | adds | P | muls | adds | P | muls | adds | ||

3 | 4 | 12 | 41 | 280 | 1140 | 241 | 3280 | 13020 | ||

5 | 10 | 34 | 43 | 256 | 1440 | 271 | 3760 | 18152 | ||

7 | 16 | 72 | 61 | 400 | 1908 | 281 | 4480 | 19036 | ||

11 | 40 | 168 | 71 | 640 | 3112 | 337 | 5248 | 22268 | ||

13 | 40 | 188 | 73 | 532 | 2504 | 379 | 6016 | 32880 | ||

17 | 82 | 274 | 109 | 940 | 5096 | 421 | 6400 | 29412 | ||

19 | 76 | 404 | 113 | 1312 | 5516 | 433 | 7708 | 32864 | ||

29 | 160 | 836 | 127 | 1216 | 6760 | 541 | 9400 | 43020 | ||

31 | 160 | 776 | 181 | 1900 | 8936 | 631 | 12160 | 56056 | ||

37 | 190 | 990 | 211 | 2560 | 12368 | 757 | 15040 | 76292 |