Cooley–Tukey FFT algorithm

2978: 2055: 6190:) time and has been the subject of much research. Also, while the permutation is a bit reversal in the radix-2 case, it is more generally an arbitrary (mixed-base) digit reversal for the mixed-radix case, and the permutation algorithms become more complicated to implement. Moreover, it is desirable on many hardware architectures to re-order intermediate stages of the FFT algorithm so that they operate on consecutive (or at least more localized) data elements. To these ends, a number of alternative implementation schemes have been devised for the Cooley–Tukey algorithm that do not require separate bit reversal and/or involve additional permutations at intermediate stages. 2973:{\displaystyle {\begin{aligned}X_{k+{\frac {N}{2}}}&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}m(k+{\frac {N}{2}})}+e^{-{\frac {2\pi i}{N}}(k+{\frac {N}{2}})}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}m(k+{\frac {N}{2}})}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}+e^{-{\frac {2\pi i}{N}}k}e^{-\pi i}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}-e^{-{\frac {2\pi i}{N}}k}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}\\&=E_{k}-e^{-{\frac {2\pi i}{N}}k}O_{k}\end{aligned}}} 1797: 1246: 1792:{\displaystyle {\begin{matrix}X_{k}=\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;even-indexed\;part\;of\;} x_{n}}{}+e^{-{\frac {2\pi i}{N}}k}\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;odd-indexed\;part\;of\;} x_{n}}=E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}\qquad {\text{ for }}k=0,\dots ,{\frac {N}{2}}-1.\end{matrix}}} 3930: 3349: 5399: 962: 4757: 3440:, ~8 digits). Rescaling the time by the number of operations, this corresponds roughly to a speedup factor of around 800,000. (To put the time for the hand calculation in perspective, 140 minutes for size 64 corresponds to an average of at most 16 seconds per floating-point operation, around 20% of which are multiplications.) 5095: 3239: 6236:

A typical strategy for in-place algorithms without auxiliary storage and without separate digit-reversal passes involves small matrix transpositions (which swap individual pairs of digits) at intermediate stages, which can be combined with the radix butterflies to reduce the number of passes over the

200:

by employing seismometers located outside the country. These sensors would generate seismological time series. However, analysis of this data would require fast algorithms for computing DFTs due to the number of sensors and length of time. This task was critical for the ratification of the proposed

4145:

merges radices 2 and 4, exploiting the fact that the first transform of radix 2 requires no twiddle factor, in order to achieve what was long the lowest known arithmetic operation count for power-of-two sizes, although recent variations achieve an even lower count. (On present-day computers,

5594:

Although the abstract Cooley–Tukey factorization of the DFT, above, applies in some form to all implementations of the algorithm, much greater diversity exists in the techniques for ordering and accessing the data at each stage of the FFT. Of special interest is the problem of devising an

205:

of IBM, recognized the potential of the method and put Tukey in touch with Cooley. However, Garwin made sure that Cooley did not know the original purpose. Instead, Cooley was told that this was needed to determine periodicities of the spin orientations in a 3-D crystal of

5101: 728: 4449: 4763: 6182:

Alternatively, some applications (such as convolution) work equally well on bit-reversed data, so one can perform forward transforms, processing, and then inverse transforms all without bit reversal to produce final results in the natural order.

3056: 3252:/2, is the core of the radix-2 DIT fast Fourier transform. The algorithm gains its speed by re-using the results of intermediate computations to compute multiple DFT outputs. Note that final outputs are obtained by a +/− combination of 250:) FFT is the simplest and most common form of the Cooley–Tukey algorithm, although highly optimized Cooley–Tukey implementations typically use other forms of the algorithm as described below. Radix-2 DIT divides a DFT of size 217:

The fact that Gauss had described the same algorithm (albeit without analyzing its asymptotic cost) was not realized until several years after Cooley and Tukey's 1965 paper. Their paper cited as inspiration only the work by

5428:(as well as mixed radices) can be employed, as was shown by both Cooley and Tukey as well as Gauss (who gave examples of radix-3 and radix-6 steps). Cooley and Tukey originally assumed that the radix butterfly required O( 4179:. The net result of all of these transpositions, for a radix-2 algorithm, corresponds to a bit reversal of the input (DIF) or output (DIT) indices. If, instead of using a small radix, one employs a radix of roughly 4097:(DIF, also called the Sande–Tukey algorithm). The version presented above was a radix-2 DIT algorithm; in the final expression, the phase multiplying the odd transform is the twiddle factor, and the +/- combination ( 366: 5912:

is pre-processed by bit-reversal.) Correspondingly, if you perform all of the steps in reverse order, you obtain a radix-2 DIF algorithm with bit reversal in post-processing (or pre-processing, respectively).

226:(PFA); although Good's algorithm was initially thought to be equivalent to the Cooley–Tukey algorithm, it was quickly realized that PFA is a quite different algorithm (working only for sizes that have 173:). Gauss did not analyze the asymptotic computational time, however. Various limited forms were also rediscovered several times throughout the 19th and early 20th centuries. FFTs became popular after 6205:

algorithm performs every stage of the FFT out-of-place, typically writing back and forth between two arrays, transposing one "digit" of the indices with each stage, and has been especially popular on

6186:

Many FFT users, however, prefer natural-order outputs, and a separate, explicit bit-reversal stage can have a non-negligible impact on the computation time, even though bit reversal can be done in O(

598: 505: 5394:{\displaystyle =\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{2}}}n_{2}k_{2}}\right)e^{-{\frac {2\pi i}{N_{1}N_{2}}}n_{1}(N_{2}k_{1}+k_{2})}} 2060: 3846:

High-performance FFT implementations make many modifications to the implementation of such an algorithm compared to this simple pseudocode. For example, one can use a larger base case than

957:{\displaystyle {\begin{matrix}X_{k}&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}\end{matrix}}} 4752:{\displaystyle X_{N_{2}k_{1}+k_{2}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{1}N_{2}}}\cdot (N_{1}n_{2}+n_{1})\cdot (N_{2}k_{1}+k_{2})}} 1949: 1013: 5090:{\displaystyle =\sum _{n_{1}=0}^{N_{1}-1}\left\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{2}}}n_{2}k_{2}}\right)e^{-{\frac {2\pi i}{N_{1}}}n_{1}k_{1}}} 3339: 4441: 3048: 1993: 4325: 4269: 4154:

considerations than by strict operation counts; well-optimized FFT implementations often employ larger radices and/or hard-coded base-case transforms of significant size.).

1844: 84: 6225:) recursion and small radices, which produces natural-order out-of-place output with no separate permutation step (as in the pseudocode above) and can be argued to have 3234:{\displaystyle {\begin{matrix}X_{k}&=&E_{k}+e^{-{\frac {2\pi i}{N}}{k}}O_{k}\\X_{k+{\frac {N}{2}}}&=&E_{k}-e^{-{\frac {2\pi i}{N}}{k}}O_{k}\end{matrix}}} 1211: 1079: 720: 3933:

The basic step of the Cooley–Tukey FFT for general factorizations can be viewed as re-interpreting a 1d DFT as something like a 2d DFT. The 1d input array of length

1142: 1043: 683: 5813: 5786: 5740: 5713: 3277: 3008: 2047: 2020: 1898: 1871: 1238: 1169: 1106: 652: 6264:(Unpublished manuscript). Werke (in Latin and German). Vol. 3. Göttingen, Germany: Königlichen Gesellschaft der Wissenschaften zu Göttingen. pp. 265–303. 3903: 3982:

direction. The transposition step can be performed in the middle, as shown here, or at the beginning or end. This is done recursively for the smaller transforms.

624:

can usually be chosen freely by the application (e.g. by changing the sample rate or window, zero-padding, etcetera), this is often not an important restriction.

415: 389: 4382:, respectively; the difference between these indexings is a transposition, as mentioned above. When this re-indexing is substituted into the DFT formula for 3345:

in this context); when this is generalized to larger radices below, the size-2 DFT is replaced by a larger DFT (which itself can be evaluated with an FFT).

123:

Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT. For example,

3909:

reasons; these and other optimizations together can improve the performance by an order of magnitude or more. (In many textbook implementations the

5742:

are combined with a size-2 DFT, those two values are overwritten by the outputs. However, the two output values should go in the first and second

4121:

implementations handle composite sizes with a variety of (typically small) factors in addition to two, usually (but not always) employing the O(

120:). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. 7256: 3843:

is required; the often-mentioned necessity of a separate bit-reversal stage only arises for certain in-place algorithms, as described below.)

6965: 6848: 6760: 5688:. Consider the last stage of a radix-2 DIT algorithm like the one presented above, where the output is written in-place over the input: when 267: 6466:

Danielson, G. C., and C. Lanczos, "Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids,"

201:

nuclear test ban so that any violations could be detected without need to visit Soviet facilities. Another participant at that meeting,

3376:; in many conventional implementations, however, the explicit recursion is avoided, and instead one traverses the computational tree in 210:. Cooley and Tukey subsequently published their joint paper, and wide adoption quickly followed due to the simultaneous development of 3975:

direction (the non-contiguous direction), then multiplies by phase factors (twiddle factors), and finally performs 1d DFTs along the

7032:) C library for computing discrete Fourier transforms in one or more dimensions, of arbitrary size, using the Cooley–Tukey algorithm 6411: 3432:

to 3–5 significant digits. Cooley and Tukey's 1965 paper reported a running time of 0.02 minutes for a size-2048 complex DFT on an

192:

Tukey reportedly came up with the idea during a meeting of President Kennedy's Science Advisory Committee discussing ways to detect

1952: 7224: 7206: 1015:

out of the second sum, as shown in the equation below. It is then clear that the two sums are the DFT of the even-indexed part

178: 7119:

Hegland, M. (1994). "A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing".

4196:, depending on the number of transpositions), initially proposed to improve memory locality, e.g. for cache optimization or 510: 5512:). This analysis was erroneous, however: the radix-butterfly is also a DFT and can be performed via an FFT algorithm in O( 3417: 423: 6213:

algorithm, which also reorders out-of-place with each stage, but this method requires separate bit/digit reversal and O(

4138: 3373: 128: 6197:: the output array is distinct from the input array or, equivalently, an equal-size auxiliary array is available. The 6355: 211: 7029: 6318: 223: 132: 36: 7084:

Qian, Z.; Lu, C.; An, M.; Tolimieri, R. (1994). "Self-sorting in-place FFT algorithm with minimum working space".

6226: 5497: 4201: 4142: 4102: 3405: 1903: 231: 189:

published a paper in 1965 reinventing the algorithm and describing how to perform it conveniently on a computer.

600:, and then combines those two results to produce the DFT of the whole sequence. This idea can then be performed 5607: 3840: 970: 6209:

architectures. Even greater potential SIMD advantages (more consecutive accesses) have been proposed for the

4134: 124: 7251: 5919:

The following is pseudocode for iterative radix-2 FFT algorithm implemented using bit-reversal permutation.

3282: 7128: 6826: 6785: 6637: 6449:

James W. Cooley, Peter A. W. Lewis, and Peter W. Welch, "Historical notes on the fast Fourier transform,"

6370: 4389: 3429: 3416:

asymptotic complexity they had achieved). The Danielson–Lanczos work predated widespread availability of

3013: 1958: 32: 5619: 4274: 4218: 3368:/2 size-2 DFTs called "butterfly" operations (so called because of the shape of the data-flow diagrams). 6257: 131:

algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the

7093: 6629: 6253: 3814: 3377: 186: 155: 143: 7234: 7216: 6375: 1805: 7133: 6831: 6790: 6642: 6551:

Duhamel, P., and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art,"

3401: 6567:

Lundy, T., and J. Van Buskirk, "A new matrix approach to real FFTs and convolutions of length 2,"

4101:) of the even and odd transforms is a size-2 DFT. (The radix's small DFT is sometimes known as a 46: 7146: 7004: 6889: 6854: 6803: 6655: 6531: 6336: 6222: 6221:) storage. One can also directly apply the Cooley–Tukey factorization definition with explicit ( 5596: 5558: 4375: 3965: 3807: 3795: 3412:

the DFT size until the transform spectrum converged (although they apparently didn't realize the

6290: 6957: 6949: 6961: 6844: 6821:

Carter, Larry; Gatlin, Kang Su (1998). "Towards an optimal bit-reversal permutation program".

6756: 6718: 6230: 3906: 3397: 3342: 1180: 1048: 688: 7138: 7101: 7066: 6994: 6881: 6836: 6795: 6647: 6521: 6380: 6326: 6286: 4106: 1117: 1018: 657: 227: 136: 40: 5791: 5764: 5718: 5691: 3255: 2986: 2025: 1998: 1876: 1849: 1216: 1147: 1084: 630: 6713:

M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In

4379: 3986:

More generally, Cooley–Tukey algorithms recursively re-express a DFT of a composite size

3918: 3856: 3393: 193: 6734:

Cooley, J. W., P. Lewis and P. Welch, "The Fast Fourier Transform and its Applications",

6426: 394: 7097: 6823:

Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)

6633: 4125:) algorithm for the prime base cases of the recursion (it is also possible to employ an 4029: 4025: 3851: 3437: 3425: 3421: 374: 202: 7245: 7150: 6872:

Rubio, M.; Gómez, P.; Drouiche, K. (2002). "A new superfast bit reversal algorithm".

6495:(C. S. Burrus, ed.), ch. 11, Rice University, Houston TX: Connexions, September 2008. 4189: 3914: 3408:

1903 work). They applied their lemma in a "backwards" recursive fashion, repeatedly

117: 7228: 7210: 7008: 6893: 6858: 6405: 4157:

Another way of looking at the Cooley–Tukey algorithm is that it re-expresses a size

3929: 6931: 6659: 6535: 5904:

post-process the output) with a bit reversal to get in-order output. (If each size-

4151: 3413: 617: 197: 174: 169:, but his work was not widely recognized (being published only posthumously and in 24: 5599:

that overwrites its input with its output data using only O(1) auxiliary storage.

5557:(32 or 64) are important in order to effectively exploit e.g. the large number of 3428:); they reported a computation time of 140 minutes for a size-64 DFT operating on 146:. Cooley and Tukey independently rediscovered and popularized it 160 years later. 154:

This algorithm, including its recursive application, was invented around 1805 by

5611: 4197: 3910: 3348: 6751:

Cormen, Thomas H.; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009).

6651: 3449: 219: 182: 28: 6840: 6675:

Gentleman W. M., and G. Sande, "Fast Fourier transforms—for fun and profit,"

6384: 4443:

cross term vanishes (its exponential is unity), and the remaining terms give

7167: 6911: 5553:

is determined by more complicated considerations. In practice, quite large

4176: 4147: 601: 170: 101: 5871:. And for next recursive stage, those 4 least significant bits will become 3404:, since the identity was noted by those two authors in 1942 (influenced by 7142: 7042:

Johnson, H. W.; Burrus, C. S. (1984). "An in-place in-order radix-2 FFT".

6999: 6982: 6722: 6614: 6526: 6509: 7182: 6715:

Proceedings of the 40th IEEE Symposium on Foundations of Computer Science

5896:, If you include all of the recursive stages of a radix-2 DIT algorithm, 3433: 207: 162: 159: 5495:

from 2 to 12 the optimal radix is found to be 3 (the closest integer to

3917:

approach, although depth-first recursion has been argued to have better

6807: 6340: 361:{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk},} 7105: 7057:

Temperton, C. (1991). "Self-sorting in-place fast Fourier transform".

7200: 7186: 6983:"An adaptation of the fast Fourier transform for parallel processing" 166: 142:

The algorithm, along with its recursive application, was invented by

7070: 6885: 6799: 6331: 6314:"An algorithm for the machine calculation of complex Fourier series" 6313: 5582:) complexity and has theoretical and practical advantages for large 6584: 5900:

the bits must be reversed and thus one must pre-process the input (

5815:

are interleaved in the even and odd elements, corresponding to the

5916:

The logarithm (log) used in this algorithm is a base 2 logarithm.

3928: 3347: 6488: 3921:.) Several of these ideas are described in further detail below. 6206: 4188:

and explicit input/output matrix transpositions, it is called a

4175:

two-dimensional DFT (plus twiddles), where the output matrix is

4117:

There are many other variations on the Cooley–Tukey algorithm.

261:

The discrete Fourier transform (DFT) is defined by the formula:

6874:

International Journal of Adaptive Control and Signal Processing

6755:(3rd ed.). Cambridge, Mass.: MIT Press. pp. 915–918. 420:

Radix-2 DIT first computes the DFTs of the even-indexed inputs

6412:"The Best of the 20th Century: Editors Name Top 10 Algorithms" 6354:

Cooley, James W.; Lewis, Peter A. W.; Welch, Peter D. (1967).

6106:

The bit-reverse-copy procedure can be implemented as follows.

5657:=32 inputs), is transferred to the index with reversed digits 234:, unlike the support for any composite size in Cooley–Tukey). 6694:

Bailey, David H., "FFTs in external or hierarchical memory,"

627:

The radix-2 DIT algorithm rearranges the DFT of the function

254:

into two interleaved DFTs (hence the name "radix-2") of size

7196: 4207:

The general Cooley–Tukey factorization rewrites the indices

6585:

A modified split-radix FFT with fewer arithmetic operations

7235:"Алгоритм БПФ по основанию два с прореживанием по частоте" 7217:"Алгоритм БПФ по основанию два с прореживанием по времени" 6260:[Theory regarding a new method of interpolation]. 5908:/2 subtransform is to operate on contiguous data, the DIT 5826:. Thus, in order to get the output in the correct place, 3905:

can be precomputed, and larger radices are often used for

135:

can be exploited for greater efficiency in separating out

4075:(which can differ between stages of the recursion). If 7023: 6776:

Karp, Alan H. (1996). "Bit reversal on uniprocessors".

3372:

This process is an example of the general technique of

5602:

The best-known reordering technique involves explicit

5590:

Data reordering, bit reversal, and in-place algorithms

3061: 1251: 733: 593:{\displaystyle (x_{2m+1}=x_{1},x_{3},\ldots ,x_{N-1})} 7191:

A simple mixed-radix Cooley–Tukey implementation in C

6408:

Special issue on "top ten algorithms of the century "

5794: 5767: 5721: 5694: 5432:) work and hence reckoned the complexity for a radix 5104: 4766: 4452: 4392: 4277: 4221: 3859: 3356:=8: a decimation-in-time radix-2 FFT breaks a length- 3285: 3258: 3059: 3016: 2989: 2058: 2028: 2001: 1961: 1906: 1879: 1852: 1808: 1249: 1219: 1183: 1150: 1120: 1087: 1051: 1021: 973: 731: 691: 660: 654:

into two parts: a sum over the even-numbered indices

633: 513: 426: 397: 377: 270: 158:, who used it to interpolate the trajectories of the 49: 7059:

SIAM Journal on Scientific and Statistical Computing

3364:/2 DFTs followed by a combining stage consisting of 500:{\displaystyle (x_{2m}=x_{0},x_{2},\ldots ,x_{N-2})} 6906:Originally attributed to Stockham in W. T. Cochran 6291:

Gauss and the history of the fast Fourier transform

3913:recursion is eliminated in favor of a nonrecursive 3341:, which is simply a size-2 DFT (sometimes called a 5807: 5780: 5734: 5707: 5561:on modern processors, and even an unbounded radix 5393: 5089: 4751: 4435: 4319: 4263: 3897: 3333: 3271: 3233: 3042: 3002: 2972: 2041: 2014: 1987: 1943: 1892: 1865: 1838: 1791: 1232: 1205: 1163: 1136: 1100: 1073: 1037: 1007: 956: 714: 677: 646: 592: 499: 409: 383: 360: 78: 6926: 6924: 6608: 6606: 6604: 6602: 6600: 5421:, and the bracketed term is the twiddle factor. 214:capable of sampling at rates up to 300 kHz. 6356:"Historical notes on the fast Fourier transform" 4200:operation, and was later shown to be an optimal 7225:"Radix-2 Decimation in Frequency FFT Algorithm" 6406:The FFT — an algorithm the whole family can use 6363:IEEE Transactions on Audio and Electroacoustics 6307: 6305: 6303: 6301: 6299: 6258:"Theoria interpolationis methodo nova tractata" 4352:of 1 or 2). That is, it re-indexes the input ( 7176:A simple, pedagogical radix-2 algorithm in C++ 6547: 6545: 3850:=1 to amortize the overhead of recursion, the 6671: 6669: 6503: 6501: 5948:the DFT of a. bit-reverse-copy(a, A) 8: 6281: 6279: 6277: 6275: 6273: 6271: 6135:complex values where n is a power of 2. 5940:complex values where n is a power of 2. 4133:algorithm for the prime base cases, such as 6690: 6688: 6483: 6481: 6479: 6293:," IEEE ASSP Magazine, 1, (4), 14–21 (1984) 6193:The problem is greatly simplified if it is 1944:{\displaystyle k=0,\dots ,{\frac {N}{2}}-1} 7207:"Radix-2 Decimation in Time FFT Algorithm" 6709: 6707: 5746:of the output array, corresponding to the 3244:This result, expressing the DFT of length 1674: 1667: 1654: 1620: 1613: 1444: 1437: 1424: 1387: 1380: 7132: 6998: 6830: 6789: 6641: 6525: 6510:"On computing the fast Fourier transform" 6374: 6330: 6312:Cooley, James W.; Tukey, John W. (1965). 5799: 5793: 5772: 5766: 5726: 5720: 5699: 5693: 5380: 5367: 5357: 5344: 5331: 5321: 5303: 5299: 5282: 5272: 5260: 5243: 5239: 5227: 5214: 5204: 5199: 5181: 5176: 5163: 5158: 5135: 5130: 5117: 5112: 5103: 5079: 5069: 5057: 5040: 5036: 5019: 5009: 4997: 4980: 4976: 4964: 4951: 4941: 4936: 4918: 4913: 4900: 4895: 4874: 4864: 4851: 4841: 4823: 4819: 4797: 4792: 4779: 4774: 4765: 4738: 4725: 4715: 4696: 4683: 4673: 4654: 4644: 4626: 4622: 4610: 4597: 4587: 4582: 4564: 4559: 4546: 4541: 4523: 4518: 4505: 4500: 4485: 4472: 4462: 4457: 4451: 4427: 4417: 4407: 4397: 4391: 4311: 4298: 4288: 4276: 4255: 4242: 4232: 4220: 3968:. One performs smaller 1d DFTs along the 3884: 3858: 3835:(The results are in the correct order in 3709:combine DFTs of two halves into full DFT: 3320: 3290: 3284: 3263: 3257: 3248:recursively in terms of two DFTs of size 3221: 3210: 3192: 3188: 3175: 3152: 3145: 3131: 3120: 3102: 3098: 3085: 3068: 3060: 3058: 3028: 3021: 3015: 2994: 2988: 2960: 2933: 2929: 2916: 2883: 2866: 2862: 2843: 2823: 2819: 2808: 2781: 2777: 2751: 2734: 2730: 2717: 2697: 2693: 2682: 2650: 2627: 2610: 2606: 2587: 2567: 2563: 2552: 2536: 2509: 2505: 2480: 2457: 2440: 2436: 2423: 2403: 2399: 2388: 2359: 2336: 2319: 2315: 2296: 2276: 2272: 2261: 2242: 2215: 2211: 2189: 2166: 2149: 2145: 2132: 2112: 2108: 2097: 2074: 2067: 2059: 2057: 2033: 2027: 2006: 2000: 1973: 1966: 1960: 1925: 1905: 1884: 1878: 1857: 1851: 1807: 1769: 1746: 1739: 1712: 1708: 1695: 1680: 1603: 1602: 1577: 1560: 1556: 1537: 1517: 1513: 1502: 1495: 1471: 1467: 1458: 1450: 1370: 1369: 1344: 1327: 1323: 1310: 1290: 1286: 1275: 1268: 1258: 1250: 1248: 1224: 1218: 1188: 1182: 1155: 1149: 1125: 1119: 1092: 1086: 1056: 1050: 1026: 1020: 1008:{\displaystyle e^{-{\frac {2\pi i}{N}}k}} 982: 978: 972: 909: 905: 886: 866: 862: 851: 809: 805: 792: 772: 768: 757: 740: 732: 730: 698: 690: 667: 659: 638: 632: 575: 556: 543: 521: 512: 482: 463: 450: 434: 425: 396: 376: 329: 325: 315: 299: 288: 275: 269: 70: 60: 48: 6615:"The Design and Implementation of FFTW3" 4105:, so-called because of the shape of the 3452:, the below procedure could be written: 685:and a sum over the odd-numbered indices 6245: 3424:(possibly with mechanical aids such as 5407:where each inner sum is a DFT of size 1953:periodicity of the complex exponential 612:). This simplified form assumes that 104:, to reduce the computation time to O( 35:(FFT) algorithm. It re-expresses the 6956:. New York: Academic Press. pp. 5524:actually cancels in the complexity O( 3334:{\displaystyle O_{k}\exp(-2\pi ik/N)} 7: 6285:Heideman, M. T., D. H. Johnson, and 4436:{\displaystyle N_{1}n_{2}N_{2}k_{1}} 3043:{\displaystyle X_{k+{\frac {N}{2}}}} 1988:{\displaystyle X_{k+{\frac {N}{2}}}} 620:; since the number of sample points 6932:FFT algorithms for vector computers 6912:What is the fast Fourier transform? 2805: 2679: 2549: 2385: 2258: 2094: 1499: 1272: 967:One can factor a common multiplier 848: 754: 604:to reduce the overall runtime to O( 7022:Frigo, Matteo; Johnson, Steven G. 6613:Frigo, M.; Johnson, S. G. (2005). 6229:locality benefits on systems with 5606:for in-place radix-2 algorithms. 5414:, each outer sum is a DFT of size 4327:, respectively, where the indices 4320:{\displaystyle n=N_{1}n_{2}+n_{1}} 4264:{\displaystyle k=N_{2}k_{1}+k_{2}} 4146:performance is determined more by 3418:mechanical or electronic computers 3383:The above re-expression of a size- 1802:Note that the equalities hold for 1671: 1668: 1664: 1661: 1658: 1655: 1651: 1648: 1645: 1642: 1639: 1636: 1633: 1627: 1624: 1621: 1617: 1614: 1610: 1607: 1604: 1441: 1438: 1434: 1431: 1428: 1425: 1421: 1418: 1415: 1412: 1409: 1406: 1403: 1397: 1394: 1391: 1388: 1384: 1381: 1377: 1374: 1371: 14: 5480:); from calculation of values of 3825:denotes the array starting with 3391:/2 DFTs is sometimes called the 1045:and the DFT of odd-indexed part 391:is an integer ranging from 0 to 16:Fast Fourier Transform algorithm 6583:Johnson, S. G., and M. Frigo, " 4071:necessarily prime), called the 1900:are calculated in this way for 1745: 7168:"Fast Fourier transform - FFT" 6508:Singleton, Richard C. (1967). 6457:(no. 10), p. 1675–1677 (1967). 5520:) operations, hence the radix 5386: 5350: 4744: 4708: 4702: 4666: 3892: 3866: 3328: 3302: 2369: 2350: 2252: 2233: 2199: 2180: 1839:{\displaystyle k=0,\dots ,N-1} 942: 927: 836: 827: 587: 514: 507:and of the odd-indexed inputs 494: 427: 258:/2 with each recursive stage. 1: 7257:Divide-and-conquer algorithms 6489:Implementing FFTs in practice 6487:S. G. Johnson and M. Frigo, " 6473:, 365–380 and 435–452 (1942). 5761:=32); whereas the two inputs 4082:is the radix, it is called a 3802:is an integer power of 2 and 3374:divide and conquer algorithms 6948:Swarztrauber, P. N. (1982). 6717:(FOCS 99), p.285-297. 1999. 4086:(DIT) algorithm, whereas if 3798:by a radix-2 DIT FFT, where 3544:trivial size-1 DFT base case 212:Analog-to-digital converters 79:{\displaystyle N=N_{1}N_{2}} 6589:IEEE Trans. Signal Process. 5614:where the data at an index 230:factors and relying on the 7273: 6918:vol. 55, 1664–1674 (1967). 6753:Introduction to algorithms 4374:two-dimensional arrays in 4161:one-dimensional DFT as an 224:prime-factor FFT algorithm 222:on what is now called the 37:discrete Fourier transform 6952:. In Rodrigue, G. (ed.). 6719:Extended abstract at IEEE 6652:10.1109/JPROC.2004.840301 5833:should take the place of 4202:cache-oblivious algorithm 3950:is reinterpreted as a 2d 232:Chinese remainder theorem 6841:10.1109/SFCS.1998.743505 6385:10.1109/tau.1967.1161903 3841:bit-reversal permutation 1846:, but the crux is that 1206:{\displaystyle x_{2m+1}} 1108:. Denote the DFT of the 1074:{\displaystyle x_{2m+1}} 715:{\displaystyle n={2m+1}} 6736:IEEE Trans on Education 6622:Proceedings of the IEEE 6493:Fast Fourier Transforms 4109:for the radix-2 case.) 4095:decimation in frequency 112:) for highly composite 7172:Cooley-Tukey technique 6950:"Vectorizing the FFTs" 5840:and the index becomes 5809: 5782: 5736: 5709: 5491:for integer values of 5395: 5194: 5148: 5091: 4931: 4810: 4753: 4577: 4536: 4437: 4321: 4265: 3983: 3899: 3369: 3352:Data flow diagram for 3335: 3273: 3235: 3044: 3004: 2974: 2838: 2712: 2582: 2418: 2291: 2127: 2043: 2016: 1995:is also obtained from 1989: 1945: 1894: 1867: 1840: 1793: 1532: 1305: 1234: 1207: 1165: 1138: 1137:{\displaystyle x_{2m}} 1102: 1075: 1039: 1038:{\displaystyle x_{2m}} 1009: 958: 881: 787: 716: 679: 678:{\displaystyle n={2m}} 648: 594: 501: 411: 385: 362: 310: 133:prime-factor algorithm 93:smaller DFTs of sizes 80: 39:(DFT) of an arbitrary 33:fast Fourier transform 21:Cooley–Tukey algorithm 7231:on November 14, 2017. 7143:10.1007/s002110050074 7121:Numerische Mathematik 7000:10.1145/321450.321457 6981:Pease, M. C. (1968). 6954:Parallel Computations 6938:vol. 1, 45–63 (1984). 6527:10.1145/363717.363771 6397:Rockmore, Daniel N., 6254:Gauss, Carl Friedrich 5810: 5808:{\displaystyle O_{k}} 5783: 5781:{\displaystyle E_{k}} 5737: 5735:{\displaystyle O_{k}} 5710: 5708:{\displaystyle E_{k}} 5396: 5154: 5108: 5092: 4891: 4770: 4754: 4537: 4496: 4438: 4322: 4266: 3932: 3900: 3749:← p + q 3351: 3336: 3274: 3272:{\displaystyle E_{k}} 3236: 3045: 3005: 3003:{\displaystyle X_{k}} 2975: 2804: 2678: 2548: 2384: 2257: 2093: 2044: 2042:{\displaystyle O_{k}} 2017: 2015:{\displaystyle E_{k}} 1990: 1946: 1895: 1893:{\displaystyle O_{k}} 1868: 1866:{\displaystyle E_{k}} 1841: 1794: 1498: 1271: 1235: 1233:{\displaystyle O_{k}} 1208: 1166: 1164:{\displaystyle E_{k}} 1139: 1103: 1101:{\displaystyle x_{n}} 1076: 1040: 1010: 959: 847: 753: 717: 680: 649: 647:{\displaystyle x_{n}} 595: 502: 412: 386: 363: 284: 81: 31:, is the most common 7213:on October 31, 2017. 7189:. 11 February 2022. 6930:P. N. Swarztrauber, 6825:. pp. 544–553. 6594:(1), 111–119 (2007). 5792: 5765: 5719: 5692: 5586:as mentioned above. 5102: 4764: 4450: 4390: 4275: 4219: 4093:is the radix, it is 4024:Multiply by complex 3898:{\displaystyle \exp} 3857: 3436:(probably in 36-bit 3360:DFT into two length- 3283: 3256: 3057: 3014: 2987: 2056: 2026: 1999: 1959: 1951:only. Thanks to the 1904: 1877: 1850: 1806: 1247: 1217: 1181: 1148: 1118: 1085: 1049: 1019: 971: 729: 689: 658: 631: 511: 424: 395: 375: 268: 246:decimation-in-time ( 238:The radix-2 DIT case 194:nuclear-weapon tests 156:Carl Friedrich Gauss 144:Carl Friedrich Gauss 47: 7098:1994ITSP...42.2835Q 6634:2005IEEEP..93..216F 6425:(4). Archived from 6231:hierarchical memory 5653:(e.g. 5 digits for 5559:processor registers 5549:), and the optimal 5424:An arbitrary radix 4067:is a small factor ( 1171:and the DFT of the 1114:ven-indexed inputs 410:{\displaystyle N-1} 7046:: 28A.2.1–28A.2.4. 6936:Parallel Computing 6201:Stockham auto-sort 5805: 5778: 5732: 5705: 5597:in-place algorithm 5501:, which minimizes 5391: 5087: 4749: 4433: 4317: 4261: 4084:decimation in time 4053:Typically, either 4028:(often called the 3984: 3966:column-major order 3895: 3422:manual calculation 3370: 3331: 3269: 3231: 3229: 3040: 3000: 2970: 2968: 2039: 2012: 1985: 1941: 1890: 1863: 1836: 1789: 1787: 1687: 1600: 1457: 1367: 1230: 1203: 1177:dd-indexed inputs 1161: 1134: 1098: 1071: 1035: 1005: 954: 952: 712: 675: 644: 590: 497: 407: 381: 358: 76: 7106:10.1109/78.324749 7092:(10): 2835–2836. 6967:978-0-12-592101-5 6850:978-0-8186-9172-0 6762:978-0-262-03384-8 6741:, 1, 28–34 (1969) 6701:(1), 23–35 (1990) 6696:J. Supercomputing 6682:, 563–578 (1966). 6553:Signal Processing 6468:J. Franklin Inst. 6399:Comput. Sci. Eng. 6112:bit-reverse-copy( 5338: 5266: 5063: 5003: 4858: 4661: 3964:matrix stored in 3208: 3160: 3118: 3036: 2949: 2892: 2797: 2760: 2636: 2525: 2466: 2367: 2345: 2250: 2231: 2197: 2175: 2082: 1981: 1933: 1777: 1749: 1728: 1586: 1496: 1494: 1487: 1353: 1269: 1267: 998: 925: 825: 384:{\displaystyle k} 345: 7264: 7238: 7232: 7227:. Archived from 7220: 7214: 7209:. Archived from 7193: 7178: 7155: 7154: 7136: 7116: 7110: 7109: 7086:IEEE Trans. ASSP 7081: 7075: 7074: 7054: 7048: 7047: 7039: 7033: 7027: 7019: 7013: 7012: 7002: 6978: 6972: 6971: 6945: 6939: 6928: 6919: 6904: 6898: 6897: 6869: 6863: 6862: 6834: 6818: 6812: 6811: 6793: 6773: 6767: 6766: 6748: 6742: 6732: 6726: 6711: 6702: 6692: 6683: 6673: 6664: 6663: 6645: 6619: 6610: 6595: 6581: 6575: 6565: 6559: 6558:, 259–299 (1990) 6549: 6540: 6539: 6529: 6505: 6496: 6485: 6474: 6464: 6458: 6447: 6441: 6440: 6438: 6437: 6431: 6416: 6410:Barry A. Cipra. 6404:(1), 60 (2000). 6395: 6389: 6388: 6378: 6360: 6351: 6345: 6344: 6334: 6309: 6294: 6283: 6266: 6265: 6250: 6204: 6203: 6022:← 1 5819:significant bit 5814: 5812: 5811: 5806: 5804: 5803: 5787: 5785: 5784: 5779: 5777: 5776: 5750:significant bit 5741: 5739: 5738: 5733: 5731: 5730: 5714: 5712: 5711: 5706: 5704: 5703: 5574:also achieves O( 5573: 5572: 5400: 5398: 5397: 5392: 5390: 5389: 5385: 5384: 5372: 5371: 5362: 5361: 5349: 5348: 5339: 5337: 5336: 5335: 5326: 5325: 5315: 5304: 5294: 5290: 5289: 5288: 5287: 5286: 5277: 5276: 5267: 5265: 5264: 5255: 5244: 5234: 5233: 5232: 5231: 5219: 5218: 5209: 5208: 5193: 5186: 5185: 5175: 5168: 5167: 5147: 5140: 5139: 5129: 5122: 5121: 5096: 5094: 5093: 5088: 5086: 5085: 5084: 5083: 5074: 5073: 5064: 5062: 5061: 5052: 5041: 5031: 5027: 5026: 5025: 5024: 5023: 5014: 5013: 5004: 5002: 5001: 4992: 4981: 4971: 4970: 4969: 4968: 4956: 4955: 4946: 4945: 4930: 4923: 4922: 4912: 4905: 4904: 4885: 4881: 4880: 4879: 4878: 4869: 4868: 4859: 4857: 4856: 4855: 4846: 4845: 4835: 4824: 4809: 4802: 4801: 4791: 4784: 4783: 4758: 4756: 4755: 4750: 4748: 4747: 4743: 4742: 4730: 4729: 4720: 4719: 4701: 4700: 4688: 4687: 4678: 4677: 4662: 4660: 4659: 4658: 4649: 4648: 4638: 4627: 4617: 4616: 4615: 4614: 4602: 4601: 4592: 4591: 4576: 4569: 4568: 4558: 4551: 4550: 4535: 4528: 4527: 4517: 4510: 4509: 4492: 4491: 4490: 4489: 4477: 4476: 4467: 4466: 4442: 4440: 4439: 4434: 4432: 4431: 4422: 4421: 4412: 4411: 4402: 4401: 4326: 4324: 4323: 4318: 4316: 4315: 4303: 4302: 4293: 4292: 4270: 4268: 4267: 4262: 4260: 4259: 4247: 4246: 4237: 4236: 4187: 4186: 4141:'s algorithm). 4107:dataflow diagram 3904: 3902: 3901: 3896: 3888: 3777: 3763:← p − q 3438:single precision 3387:DFT as two size- 3340: 3338: 3337: 3332: 3324: 3295: 3294: 3278: 3276: 3275: 3270: 3268: 3267: 3240: 3238: 3237: 3232: 3230: 3226: 3225: 3216: 3215: 3214: 3209: 3204: 3193: 3180: 3179: 3163: 3162: 3161: 3153: 3136: 3135: 3126: 3125: 3124: 3119: 3114: 3103: 3090: 3089: 3073: 3072: 3049: 3047: 3046: 3041: 3039: 3038: 3037: 3029: 3009: 3007: 3006: 3001: 2999: 2998: 2979: 2977: 2976: 2971: 2969: 2965: 2964: 2955: 2954: 2950: 2945: 2934: 2921: 2920: 2905: 2901: 2900: 2893: 2891: 2887: 2878: 2867: 2857: 2856: 2837: 2827: 2818: 2803: 2802: 2798: 2793: 2782: 2769: 2768: 2761: 2759: 2755: 2746: 2735: 2725: 2724: 2711: 2701: 2692: 2671: 2667: 2666: 2645: 2644: 2637: 2635: 2631: 2622: 2611: 2601: 2600: 2581: 2571: 2562: 2547: 2546: 2531: 2530: 2526: 2521: 2510: 2497: 2496: 2475: 2474: 2467: 2465: 2461: 2452: 2441: 2431: 2430: 2417: 2407: 2398: 2377: 2373: 2372: 2368: 2360: 2346: 2344: 2340: 2331: 2320: 2310: 2309: 2290: 2280: 2271: 2256: 2255: 2251: 2243: 2232: 2227: 2216: 2203: 2202: 2198: 2190: 2176: 2174: 2170: 2161: 2150: 2140: 2139: 2126: 2116: 2107: 2085: 2084: 2083: 2075: 2048: 2046: 2045: 2040: 2038: 2037: 2021: 2019: 2018: 2013: 2011: 2010: 1994: 1992: 1991: 1986: 1984: 1983: 1982: 1974: 1950: 1948: 1947: 1942: 1934: 1926: 1899: 1897: 1896: 1891: 1889: 1888: 1872: 1870: 1869: 1864: 1862: 1861: 1845: 1843: 1842: 1837: 1798: 1796: 1795: 1790: 1788: 1778: 1770: 1750: 1747: 1744: 1743: 1734: 1733: 1729: 1724: 1713: 1700: 1699: 1686: 1685: 1684: 1675: 1601: 1596: 1595: 1594: 1587: 1585: 1581: 1572: 1561: 1551: 1550: 1531: 1521: 1512: 1493: 1492: 1488: 1483: 1472: 1459: 1456: 1455: 1454: 1445: 1368: 1363: 1362: 1361: 1354: 1352: 1348: 1339: 1328: 1318: 1317: 1304: 1294: 1285: 1263: 1262: 1239: 1237: 1236: 1231: 1229: 1228: 1212: 1210: 1209: 1204: 1202: 1201: 1170: 1168: 1167: 1162: 1160: 1159: 1143: 1141: 1140: 1135: 1133: 1132: 1107: 1105: 1104: 1099: 1097: 1096: 1081:of the function 1080: 1078: 1077: 1072: 1070: 1069: 1044: 1042: 1041: 1036: 1034: 1033: 1014: 1012: 1011: 1006: 1004: 1003: 999: 994: 983: 963: 961: 960: 955: 953: 949: 948: 926: 921: 910: 900: 899: 880: 870: 861: 843: 842: 826: 821: 810: 800: 799: 786: 776: 767: 745: 744: 721: 719: 718: 713: 711: 684: 682: 681: 676: 674: 653: 651: 650: 645: 643: 642: 599: 597: 596: 591: 586: 585: 561: 560: 548: 547: 535: 534: 506: 504: 503: 498: 493: 492: 468: 467: 455: 454: 442: 441: 416: 414: 413: 408: 390: 388: 387: 382: 367: 365: 364: 359: 354: 353: 346: 341: 330: 320: 319: 309: 298: 280: 279: 228:relatively prime 137:relatively prime 85: 83: 82: 77: 75: 74: 65: 64: 7272: 7271: 7267: 7266: 7265: 7263: 7262: 7261: 7242: 7241: 7233: 7223: 7215: 7205: 7181: 7174:. Article. 10. 7166: 7163: 7158: 7118: 7117: 7113: 7083: 7082: 7078: 7071:10.1137/0912043 7056: 7055: 7051: 7041: 7040: 7036: 7021: 7020: 7016: 6980: 6979: 6975: 6968: 6947: 6946: 6942: 6929: 6922: 6905: 6901: 6886:10.1002/acs.718 6880:(10): 703–707. 6871: 6870: 6866: 6851: 6820: 6819: 6815: 6800:10.1137/1038001 6775: 6774: 6770: 6763: 6750: 6749: 6745: 6733: 6729: 6712: 6705: 6693: 6686: 6674: 6667: 6617: 6612: 6611: 6598: 6582: 6578: 6574:, 23–45 (2007). 6566: 6562: 6550: 6543: 6520:(10): 647–654. 6507: 6506: 6499: 6486: 6477: 6465: 6461: 6448: 6444: 6435: 6433: 6429: 6414: 6409: 6396: 6392: 6376:10.1.1.467.7209 6358: 6353: 6352: 6348: 6332:10.2307/2003354 6325:(90): 297–301. 6311: 6310: 6297: 6284: 6269: 6252: 6251: 6247: 6243: 6227:cache-oblivious 6199: 6198: 6180: 6104: 6097: 5986: 5895: 5889: 5883: 5877: 5870: 5864: 5858: 5852: 5846: 5839: 5832: 5825: 5795: 5790: 5789: 5768: 5763: 5762: 5756: 5722: 5717: 5716: 5695: 5690: 5689: 5687: 5681: 5675: 5669: 5663: 5652: 5646: 5640: 5634: 5628: 5592: 5578: log 5568: 5566: 5545: 5508: 5487: 5476: 5464: 5453: 5420: 5413: 5376: 5363: 5353: 5340: 5327: 5317: 5316: 5305: 5295: 5278: 5268: 5256: 5245: 5235: 5223: 5210: 5200: 5195: 5177: 5159: 5153: 5149: 5131: 5113: 5100: 5099: 5075: 5065: 5053: 5042: 5032: 5015: 5005: 4993: 4982: 4972: 4960: 4947: 4937: 4932: 4914: 4896: 4890: 4886: 4870: 4860: 4847: 4837: 4836: 4825: 4815: 4811: 4793: 4775: 4762: 4761: 4734: 4721: 4711: 4692: 4679: 4669: 4650: 4640: 4639: 4628: 4618: 4606: 4593: 4583: 4578: 4560: 4542: 4519: 4501: 4481: 4468: 4458: 4453: 4448: 4447: 4423: 4413: 4403: 4393: 4388: 4387: 4380:row-major order 4373: 4366: 4347: 4340: 4333: 4307: 4294: 4284: 4273: 4272: 4251: 4238: 4228: 4217: 4216: 4182: 4180: 4174: 4167: 4129: log 4115: 4092: 4081: 4066: 4059: 4048: 4041: 4030:twiddle factors 4020: 4013: 4002: 3996: 3981: 3974: 3963: 3956: 3949: 3943: 3927: 3919:memory locality 3855: 3854: 3852:twiddle factors 3839:and no further 3830: 3773: 3770: 3762: 3754: 3747: 3742: 3734: 3716: 3692: 3678: 3671: 3665: 3658: 3651: 3629: 3621: 3615: 3601: 3591: 3581: 3558: 3542: 3535: 3518: 3504: 3493: 3487: 3481:): 3464: 3446: 3426:adding machines 3286: 3281: 3280: 3259: 3254: 3253: 3228: 3227: 3217: 3194: 3184: 3171: 3169: 3164: 3141: 3138: 3137: 3127: 3104: 3094: 3081: 3079: 3074: 3064: 3055: 3054: 3017: 3012: 3011: 2990: 2985: 2984: 2983:We can rewrite 2967: 2966: 2956: 2935: 2925: 2912: 2903: 2902: 2879: 2868: 2858: 2839: 2783: 2773: 2747: 2736: 2726: 2713: 2669: 2668: 2646: 2623: 2612: 2602: 2583: 2532: 2511: 2501: 2476: 2453: 2442: 2432: 2419: 2375: 2374: 2332: 2321: 2311: 2292: 2217: 2207: 2162: 2151: 2141: 2128: 2086: 2063: 2054: 2053: 2029: 2024: 2023: 2002: 1997: 1996: 1962: 1957: 1956: 1902: 1901: 1880: 1875: 1874: 1853: 1848: 1847: 1804: 1803: 1786: 1785: 1748: for 1735: 1714: 1704: 1691: 1676: 1573: 1562: 1552: 1533: 1497: 1473: 1463: 1446: 1340: 1329: 1319: 1306: 1270: 1254: 1245: 1244: 1240:and we obtain: 1220: 1215: 1214: 1184: 1179: 1178: 1151: 1146: 1145: 1121: 1116: 1115: 1088: 1083: 1082: 1052: 1047: 1046: 1022: 1017: 1016: 984: 974: 969: 968: 951: 950: 911: 901: 882: 811: 801: 788: 751: 746: 736: 727: 726: 687: 686: 656: 655: 634: 629: 628: 571: 552: 539: 517: 509: 508: 478: 459: 446: 430: 422: 421: 393: 392: 373: 372: 331: 321: 311: 271: 266: 265: 240: 152: 99: 92: 66: 56: 45: 44: 17: 12: 11: 5: 7270: 7268: 7260: 7259: 7254: 7252:FFT algorithms 7244: 7243: 7240: 7239: 7221: 7203: 7194: 7179: 7162: 7161:External links 7159: 7157: 7156: 7134:10.1.1.54.5659 7127:(4): 507–547. 7111: 7076: 7065:(4): 808–823. 7049: 7034: 7014: 6993:(2): 252–264. 6973: 6966: 6940: 6920: 6899: 6864: 6849: 6832:10.1.1.46.9319 6813: 6791:10.1.1.24.2913 6768: 6761: 6743: 6727: 6703: 6684: 6665: 6643:10.1.1.66.3097 6628:(2): 216–231. 6596: 6576: 6560: 6541: 6497: 6475: 6459: 6442: 6390: 6346: 6295: 6267: 6244: 6242: 6239: 6108: 6093: 5982: 5925:iterative-fft 5921: 5893: 5887: 5881: 5875: 5868: 5862: 5856: 5850: 5844: 5837: 5830: 5823: 5802: 5798: 5775: 5771: 5754: 5729: 5725: 5702: 5698: 5685: 5679: 5673: 5667: 5661: 5650: 5644: 5638: 5632: 5626: 5591: 5588: 5541: 5506: 5485: 5474: 5462: 5449: 5418: 5411: 5405: 5404: 5403: 5402: 5388: 5383: 5379: 5375: 5370: 5366: 5360: 5356: 5352: 5347: 5343: 5334: 5330: 5324: 5320: 5314: 5311: 5308: 5302: 5298: 5293: 5285: 5281: 5275: 5271: 5263: 5259: 5254: 5251: 5248: 5242: 5238: 5230: 5226: 5222: 5217: 5213: 5207: 5203: 5198: 5192: 5189: 5184: 5180: 5174: 5171: 5166: 5162: 5157: 5152: 5146: 5143: 5138: 5134: 5128: 5125: 5120: 5116: 5111: 5107: 5097: 5082: 5078: 5072: 5068: 5060: 5056: 5051: 5048: 5045: 5039: 5035: 5030: 5022: 5018: 5012: 5008: 5000: 4996: 4991: 4988: 4985: 4979: 4975: 4967: 4963: 4959: 4954: 4950: 4944: 4940: 4935: 4929: 4926: 4921: 4917: 4911: 4908: 4903: 4899: 4894: 4889: 4884: 4877: 4873: 4867: 4863: 4854: 4850: 4844: 4840: 4834: 4831: 4828: 4822: 4818: 4814: 4808: 4805: 4800: 4796: 4790: 4787: 4782: 4778: 4773: 4769: 4746: 4741: 4737: 4733: 4728: 4724: 4718: 4714: 4710: 4707: 4704: 4699: 4695: 4691: 4686: 4682: 4676: 4672: 4668: 4665: 4657: 4653: 4647: 4643: 4637: 4634: 4631: 4625: 4621: 4613: 4609: 4605: 4600: 4596: 4590: 4586: 4581: 4575: 4572: 4567: 4563: 4557: 4554: 4549: 4545: 4540: 4534: 4531: 4526: 4522: 4516: 4513: 4508: 4504: 4499: 4495: 4488: 4484: 4480: 4475: 4471: 4465: 4461: 4456: 4430: 4426: 4420: 4416: 4410: 4406: 4400: 4396: 4371: 4364: 4356:) and output ( 4345: 4338: 4331: 4314: 4310: 4306: 4301: 4297: 4291: 4287: 4283: 4280: 4258: 4254: 4250: 4245: 4241: 4235: 4231: 4227: 4224: 4192:algorithm (or 4172: 4165: 4114: 4111: 4090: 4079: 4064: 4057: 4051: 4050: 4046: 4039: 4033: 4026:roots of unity 4022: 4018: 4011: 4000: 3994: 3979: 3972: 3961: 3954: 3947: 3941: 3926: 3923: 3894: 3891: 3887: 3883: 3880: 3877: 3874: 3871: 3868: 3865: 3862: 3828: 3786:,1), computes 3756: 3752: 3745: 3736: 3732: 3714: 3683: 3673: 3669: 3660: 3656: 3649: 3623: 3619: 3606: 3596: 3586: 3579: 3575:) 3552: 3540: 3533: 3509: 3499: 3491: 3485: 3458: 3454: 3445: 3442: 3330: 3327: 3323: 3319: 3316: 3313: 3310: 3307: 3304: 3301: 3298: 3293: 3289: 3266: 3262: 3242: 3241: 3224: 3220: 3213: 3207: 3203: 3200: 3197: 3191: 3187: 3183: 3178: 3174: 3170: 3168: 3165: 3159: 3156: 3151: 3148: 3144: 3140: 3139: 3134: 3130: 3123: 3117: 3113: 3110: 3107: 3101: 3097: 3093: 3088: 3084: 3080: 3078: 3075: 3071: 3067: 3063: 3062: 3035: 3032: 3027: 3024: 3020: 2997: 2993: 2981: 2980: 2963: 2959: 2953: 2948: 2944: 2941: 2938: 2932: 2928: 2924: 2919: 2915: 2911: 2908: 2906: 2904: 2899: 2896: 2890: 2886: 2882: 2877: 2874: 2871: 2865: 2861: 2855: 2852: 2849: 2846: 2842: 2836: 2833: 2830: 2826: 2822: 2817: 2814: 2811: 2807: 2801: 2796: 2792: 2789: 2786: 2780: 2776: 2772: 2767: 2764: 2758: 2754: 2750: 2745: 2742: 2739: 2733: 2729: 2723: 2720: 2716: 2710: 2707: 2704: 2700: 2696: 2691: 2688: 2685: 2681: 2677: 2674: 2672: 2670: 2665: 2662: 2659: 2656: 2653: 2649: 2643: 2640: 2634: 2630: 2626: 2621: 2618: 2615: 2609: 2605: 2599: 2596: 2593: 2590: 2586: 2580: 2577: 2574: 2570: 2566: 2561: 2558: 2555: 2551: 2545: 2542: 2539: 2535: 2529: 2524: 2520: 2517: 2514: 2508: 2504: 2500: 2495: 2492: 2489: 2486: 2483: 2479: 2473: 2470: 2464: 2460: 2456: 2451: 2448: 2445: 2439: 2435: 2429: 2426: 2422: 2416: 2413: 2410: 2406: 2402: 2397: 2394: 2391: 2387: 2383: 2380: 2378: 2376: 2371: 2366: 2363: 2358: 2355: 2352: 2349: 2343: 2339: 2335: 2330: 2327: 2324: 2318: 2314: 2308: 2305: 2302: 2299: 2295: 2289: 2286: 2283: 2279: 2275: 2270: 2267: 2264: 2260: 2254: 2249: 2246: 2241: 2238: 2235: 2230: 2226: 2223: 2220: 2214: 2210: 2206: 2201: 2196: 2193: 2188: 2185: 2182: 2179: 2173: 2169: 2165: 2160: 2157: 2154: 2148: 2144: 2138: 2135: 2131: 2125: 2122: 2119: 2115: 2111: 2106: 2103: 2100: 2096: 2092: 2089: 2087: 2081: 2078: 2073: 2070: 2066: 2062: 2061: 2036: 2032: 2009: 2005: 1980: 1977: 1972: 1969: 1965: 1940: 1937: 1932: 1929: 1924: 1921: 1918: 1915: 1912: 1909: 1887: 1883: 1860: 1856: 1835: 1832: 1829: 1826: 1823: 1820: 1817: 1814: 1811: 1800: 1799: 1784: 1781: 1776: 1773: 1768: 1765: 1762: 1759: 1756: 1753: 1742: 1738: 1732: 1727: 1723: 1720: 1717: 1711: 1707: 1703: 1698: 1694: 1690: 1683: 1679: 1673: 1670: 1666: 1663: 1660: 1657: 1653: 1650: 1647: 1644: 1641: 1638: 1635: 1632: 1629: 1626: 1623: 1619: 1616: 1612: 1609: 1606: 1599: 1593: 1590: 1584: 1580: 1576: 1571: 1568: 1565: 1559: 1555: 1549: 1546: 1543: 1540: 1536: 1530: 1527: 1524: 1520: 1516: 1511: 1508: 1505: 1501: 1491: 1486: 1482: 1479: 1476: 1470: 1466: 1462: 1453: 1449: 1443: 1440: 1436: 1433: 1430: 1427: 1423: 1420: 1417: 1414: 1411: 1408: 1405: 1402: 1399: 1396: 1393: 1390: 1386: 1383: 1379: 1376: 1373: 1366: 1360: 1357: 1351: 1347: 1343: 1338: 1335: 1332: 1326: 1322: 1316: 1313: 1309: 1303: 1300: 1297: 1293: 1289: 1284: 1281: 1278: 1274: 1266: 1261: 1257: 1253: 1252: 1227: 1223: 1200: 1197: 1194: 1191: 1187: 1158: 1154: 1131: 1128: 1124: 1095: 1091: 1068: 1065: 1062: 1059: 1055: 1032: 1029: 1025: 1002: 997: 993: 990: 987: 981: 977: 965: 964: 947: 944: 941: 938: 935: 932: 929: 924: 920: 917: 914: 908: 904: 898: 895: 892: 889: 885: 879: 876: 873: 869: 865: 860: 857: 854: 850: 846: 841: 838: 835: 832: 829: 824: 820: 817: 814: 808: 804: 798: 795: 791: 785: 782: 779: 775: 771: 766: 763: 760: 756: 752: 750: 747: 743: 739: 735: 734: 710: 707: 704: 701: 697: 694: 673: 670: 666: 663: 641: 637: 589: 584: 581: 578: 574: 570: 567: 564: 559: 555: 551: 546: 542: 538: 533: 530: 527: 524: 520: 516: 496: 491: 488: 485: 481: 477: 474: 471: 466: 462: 458: 453: 449: 445: 440: 437: 433: 429: 406: 403: 400: 380: 369: 368: 357: 352: 349: 344: 340: 337: 334: 328: 324: 318: 314: 308: 305: 302: 297: 294: 291: 287: 283: 278: 274: 239: 236: 203:Richard Garwin 151: 148: 118:smooth numbers 97: 90: 73: 69: 63: 59: 55: 52: 23:, named after 15: 13: 10: 9: 6: 4: 3: 2: 7269: 7258: 7255: 7253: 7250: 7249: 7247: 7237:(in Russian). 7236: 7230: 7226: 7222: 7219:(in Russian). 7218: 7212: 7208: 7204: 7202: 7198: 7195: 7192: 7188: 7184: 7180: 7177: 7173: 7169: 7165: 7164: 7160: 7152: 7148: 7144: 7140: 7135: 7130: 7126: 7122: 7115: 7112: 7107: 7103: 7099: 7095: 7091: 7087: 7080: 7077: 7072: 7068: 7064: 7060: 7053: 7050: 7045: 7038: 7035: 7031: 7025: 7018: 7015: 7010: 7006: 7001: 6996: 6992: 6988: 6984: 6977: 6974: 6969: 6963: 6959: 6955: 6951: 6944: 6941: 6937: 6933: 6927: 6925: 6921: 6917: 6913: 6909: 6903: 6900: 6895: 6891: 6887: 6883: 6879: 6875: 6868: 6865: 6860: 6856: 6852: 6846: 6842: 6838: 6833: 6828: 6824: 6817: 6814: 6809: 6805: 6801: 6797: 6792: 6787: 6783: 6779: 6772: 6769: 6764: 6758: 6754: 6747: 6744: 6740: 6737: 6731: 6728: 6724: 6720: 6716: 6710: 6708: 6704: 6700: 6697: 6691: 6689: 6685: 6681: 6678: 6672: 6670: 6666: 6661: 6657: 6653: 6649: 6644: 6639: 6635: 6631: 6627: 6623: 6616: 6609: 6607: 6605: 6603: 6601: 6597: 6593: 6590: 6586: 6580: 6577: 6573: 6570: 6564: 6561: 6557: 6554: 6548: 6546: 6542: 6537: 6533: 6528: 6523: 6519: 6515: 6511: 6504: 6502: 6498: 6494: 6490: 6484: 6482: 6480: 6476: 6472: 6469: 6463: 6460: 6456: 6452: 6446: 6443: 6432:on 2009-04-07 6428: 6424: 6420: 6413: 6407: 6403: 6400: 6394: 6391: 6386: 6382: 6377: 6372: 6368: 6364: 6357: 6350: 6347: 6342: 6338: 6333: 6328: 6324: 6321: 6320: 6319:Math. Comput. 6315: 6308: 6306: 6304: 6302: 6300: 6296: 6292: 6288: 6282: 6280: 6278: 6276: 6274: 6272: 6268: 6263: 6259: 6255: 6249: 6246: 6240: 6238: 6234: 6232: 6228: 6224: 6220: 6216: 6212: 6208: 6202: 6196: 6191: 6189: 6184: 6179: 6175: 6172: 6168: 6165: 6161: 6158: 6154: 6150: 6146: 6142: 6138: 6134: 6130: 6126: 6123: 6119: 6115: 6111: 6107: 6103: 6100: 6096: 6092: 6089: 6085: 6082: 6078: 6074: 6071: 6067: 6063: 6060: 6056: 6053: 6050: 6046: 6043: 6039: 6035: 6032: 6028: 6025: 6021: 6018: 6015: 6012: 6008: 6005: 6001: 5998: 5994: 5990: 5985: 5981: 5977: 5974: 5970: 5966: 5962: 5959: 5956:.length 5955: 5951: 5947: 5943: 5939: 5935: 5931: 5928: 5924: 5920: 5917: 5914: 5911: 5907: 5903: 5899: 5892: 5886: 5880: 5874: 5867: 5861: 5855: 5849: 5843: 5836: 5829: 5822: 5818: 5800: 5796: 5773: 5769: 5760: 5753: 5749: 5745: 5727: 5723: 5700: 5696: 5684: 5678: 5672: 5666: 5660: 5656: 5649: 5643: 5637: 5631: 5625: 5621: 5618:, written in 5617: 5613: 5609: 5605: 5600: 5598: 5589: 5587: 5585: 5581: 5577: 5571: 5564: 5560: 5556: 5552: 5548: 5544: 5539: 5535: 5531: 5527: 5523: 5519: 5515: 5511: 5504: 5500: 5499: 5494: 5490: 5483: 5479: 5472: 5468: 5460: 5456: 5452: 5447: 5443: 5439: 5435: 5431: 5427: 5422: 5417: 5410: 5381: 5377: 5373: 5368: 5364: 5358: 5354: 5345: 5341: 5332: 5328: 5322: 5318: 5312: 5309: 5306: 5300: 5296: 5291: 5283: 5279: 5273: 5269: 5261: 5257: 5252: 5249: 5246: 5240: 5236: 5228: 5224: 5220: 5215: 5211: 5205: 5201: 5196: 5190: 5187: 5182: 5178: 5172: 5169: 5164: 5160: 5155: 5150: 5144: 5141: 5136: 5132: 5126: 5123: 5118: 5114: 5109: 5105: 5098: 5080: 5076: 5070: 5066: 5058: 5054: 5049: 5046: 5043: 5037: 5033: 5028: 5020: 5016: 5010: 5006: 4998: 4994: 4989: 4986: 4983: 4977: 4973: 4965: 4961: 4957: 4952: 4948: 4942: 4938: 4933: 4927: 4924: 4919: 4915: 4909: 4906: 4901: 4897: 4892: 4887: 4882: 4875: 4871: 4865: 4861: 4852: 4848: 4842: 4838: 4832: 4829: 4826: 4820: 4816: 4812: 4806: 4803: 4798: 4794: 4788: 4785: 4780: 4776: 4771: 4767: 4760: 4759: 4739: 4735: 4731: 4726: 4722: 4716: 4712: 4705: 4697: 4693: 4689: 4684: 4680: 4674: 4670: 4663: 4655: 4651: 4645: 4641: 4635: 4632: 4629: 4623: 4619: 4611: 4607: 4603: 4598: 4594: 4588: 4584: 4579: 4573: 4570: 4565: 4561: 4555: 4552: 4547: 4543: 4538: 4532: 4529: 4524: 4520: 4514: 4511: 4506: 4502: 4497: 4493: 4486: 4482: 4478: 4473: 4469: 4463: 4459: 4454: 4446: 4445: 4444: 4428: 4424: 4418: 4414: 4408: 4404: 4398: 4394: 4385: 4381: 4377: 4370: 4363: 4359: 4355: 4351: 4344: 4337: 4330: 4312: 4308: 4304: 4299: 4295: 4289: 4285: 4281: 4278: 4256: 4252: 4248: 4243: 4239: 4233: 4229: 4225: 4222: 4214: 4210: 4205: 4203: 4199: 4195: 4191: 4190:four-step FFT 4185: 4178: 4171: 4164: 4160: 4155: 4153: 4149: 4144: 4140: 4136: 4132: 4128: 4124: 4120: 4112: 4110: 4108: 4104: 4100: 4096: 4089: 4085: 4078: 4074: 4070: 4063: 4056: 4045: 4042:DFTs of size 4038: 4034: 4031: 4027: 4023: 4017: 4014:DFTs of size 4010: 4006: 4005: 4004: 3999: 3993: 3989: 3978: 3971: 3967: 3960: 3953: 3946: 3940: 3936: 3931: 3924: 3922: 3920: 3916: 3915:breadth-first 3912: 3908: 3889: 3885: 3881: 3878: 3875: 3872: 3869: 3863: 3860: 3853: 3849: 3844: 3842: 3838: 3833: 3831: 3824: 3820: 3816: 3813: 3810:of the input 3809: 3805: 3801: 3797: 3793: 3789: 3785: 3781: 3776: 3769: 3766: 3760: 3755: 3748: 3740: 3735: 3728: 3725: 3721: 3717: 3710: 3707: 3703: 3699: 3696: 3691: 3687: 3682: 3677: 3672: 3664: 3659: 3652: 3645: 3641: 3637: 3633: 3627: 3622: 3614: 3610: 3605: 3600: 3595: 3590: 3585: 3578: 3574: 3570: 3566: 3562: 3556: 3551: 3548: 3545: 3539: 3532: 3529: 3525: 3522: 3517: 3513: 3508: 3503: 3498: 3494: 3484: 3480: 3476: 3472: 3468: 3462: 3457: 3453: 3451: 3443: 3441: 3439: 3435: 3431: 3427: 3423: 3420:and required 3419: 3415: 3411: 3407: 3403: 3400: 3399: 3395: 3390: 3386: 3381: 3379: 3378:breadth-first 3375: 3367: 3363: 3359: 3355: 3350: 3346: 3344: 3325: 3321: 3317: 3314: 3311: 3308: 3305: 3299: 3296: 3291: 3287: 3264: 3260: 3251: 3247: 3222: 3218: 3211: 3205: 3201: 3198: 3195: 3189: 3185: 3181: 3176: 3172: 3166: 3157: 3154: 3149: 3146: 3142: 3132: 3128: 3121: 3115: 3111: 3108: 3105: 3099: 3095: 3091: 3086: 3082: 3076: 3069: 3065: 3053: 3052: 3051: 3033: 3030: 3025: 3022: 3018: 2995: 2991: 2961: 2957: 2951: 2946: 2942: 2939: 2936: 2930: 2926: 2922: 2917: 2913: 2909: 2907: 2897: 2894: 2888: 2884: 2880: 2875: 2872: 2869: 2863: 2859: 2853: 2850: 2847: 2844: 2840: 2834: 2831: 2828: 2824: 2820: 2815: 2812: 2809: 2799: 2794: 2790: 2787: 2784: 2778: 2774: 2770: 2765: 2762: 2756: 2752: 2748: 2743: 2740: 2737: 2731: 2727: 2721: 2718: 2714: 2708: 2705: 2702: 2698: 2694: 2689: 2686: 2683: 2675: 2673: 2663: 2660: 2657: 2654: 2651: 2647: 2641: 2638: 2632: 2628: 2624: 2619: 2616: 2613: 2607: 2603: 2597: 2594: 2591: 2588: 2584: 2578: 2575: 2572: 2568: 2564: 2559: 2556: 2553: 2543: 2540: 2537: 2533: 2527: 2522: 2518: 2515: 2512: 2506: 2502: 2498: 2493: 2490: 2487: 2484: 2481: 2477: 2471: 2468: 2462: 2458: 2454: 2449: 2446: 2443: 2437: 2433: 2427: 2424: 2420: 2414: 2411: 2408: 2404: 2400: 2395: 2392: 2389: 2381: 2379: 2364: 2361: 2356: 2353: 2347: 2341: 2337: 2333: 2328: 2325: 2322: 2316: 2312: 2306: 2303: 2300: 2297: 2293: 2287: 2284: 2281: 2277: 2273: 2268: 2265: 2262: 2247: 2244: 2239: 2236: 2228: 2224: 2221: 2218: 2212: 2208: 2204: 2194: 2191: 2186: 2183: 2177: 2171: 2167: 2163: 2158: 2155: 2152: 2146: 2142: 2136: 2133: 2129: 2123: 2120: 2117: 2113: 2109: 2104: 2101: 2098: 2090: 2088: 2079: 2076: 2071: 2068: 2064: 2052: 2051: 2050: 2034: 2030: 2007: 2003: 1978: 1975: 1970: 1967: 1963: 1954: 1938: 1935: 1930: 1927: 1922: 1919: 1916: 1913: 1910: 1907: 1885: 1881: 1858: 1854: 1833: 1830: 1827: 1824: 1821: 1818: 1815: 1812: 1809: 1782: 1779: 1774: 1771: 1766: 1763: 1760: 1757: 1754: 1751: 1740: 1736: 1730: 1725: 1721: 1718: 1715: 1709: 1705: 1701: 1696: 1692: 1688: 1681: 1677: 1630: 1597: 1591: 1588: 1582: 1578: 1574: 1569: 1566: 1563: 1557: 1553: 1547: 1544: 1541: 1538: 1534: 1528: 1525: 1522: 1518: 1514: 1509: 1506: 1503: 1489: 1484: 1480: 1477: 1474: 1468: 1464: 1460: 1451: 1447: 1400: 1364: 1358: 1355: 1349: 1345: 1341: 1336: 1333: 1330: 1324: 1320: 1314: 1311: 1307: 1301: 1298: 1295: 1291: 1287: 1282: 1279: 1276: 1264: 1259: 1255: 1243: 1242: 1241: 1225: 1221: 1198: 1195: 1192: 1189: 1185: 1176: 1175: 1156: 1152: 1129: 1126: 1122: 1113: 1112: 1093: 1089: 1066: 1063: 1060: 1057: 1053: 1030: 1027: 1023: 1000: 995: 991: 988: 985: 979: 975: 945: 939: 936: 933: 930: 922: 918: 915: 912: 906: 902: 896: 893: 890: 887: 883: 877: 874: 871: 867: 863: 858: 855: 852: 844: 839: 833: 830: 822: 818: 815: 812: 806: 802: 796: 793: 789: 783: 780: 777: 773: 769: 764: 761: 758: 748: 741: 737: 725: 724: 723: 708: 705: 702: 699: 695: 692: 671: 668: 664: 661: 639: 635: 625: 623: 619: 615: 611: 607: 603: 582: 579: 576: 572: 568: 565: 562: 557: 553: 549: 544: 540: 536: 531: 528: 525: 522: 518: 489: 486: 483: 479: 475: 472: 469: 464: 460: 456: 451: 447: 443: 438: 435: 431: 418: 404: 401: 398: 378: 355: 350: 347: 342: 338: 335: 332: 326: 322: 316: 312: 306: 303: 300: 295: 292: 289: 285: 281: 276: 272: 264: 263: 262: 259: 257: 253: 249: 245: 237: 235: 233: 229: 225: 221: 215: 213: 209: 204: 199: 195: 190: 188: 184: 180: 176: 172: 168: 164: 161: 157: 149: 147: 145: 140: 138: 134: 130: 126: 121: 119: 115: 111: 107: 103: 96: 89: 71: 67: 61: 57: 53: 50: 42: 38: 34: 30: 26: 22: 7229:the original 7211:the original 7190: 7175: 7171: 7124: 7120: 7114: 7089: 7085: 7079: 7062: 7058: 7052: 7044:Proc. ICASSP 7043: 7037: 7017: 6990: 6986: 6976: 6953: 6943: 6935: 6915: 6907: 6902: 6877: 6873: 6867: 6822: 6816: 6781: 6777: 6771: 6752: 6746: 6738: 6735: 6730: 6714: 6698: 6695: 6679: 6676: 6625: 6621: 6591: 6588: 6579: 6571: 6568: 6563: 6555: 6552: 6517: 6513: 6492: 6470: 6467: 6462: 6454: 6450: 6445: 6434:. Retrieved 6427:the original 6422: 6418: 6401: 6398: 6393: 6369:(2): 76–79. 6366: 6362: 6349: 6322: 6317: 6287:C. S. Burrus 6261: 6248: 6235: 6218: 6214: 6210: 6200: 6195:out-of-place 6194: 6192: 6187: 6185: 6181: 6177: 6173: 6170: 6166: 6163: 6159: 6156: 6155:.length 6152: 6148: 6144: 6140: 6136: 6132: 6128: 6124: 6121: 6117: 6113: 6109: 6105: 6101: 6098: 6094: 6090: 6087: 6083: 6080: 6076: 6072: 6069: 6065: 6061: 6058: 6054: 6051: 6048: 6044: 6041: 6037: 6033: 6030: 6026: 6023: 6019: 6016: 6013: 6010: 6006: 6003: 5999: 5996: 5992: 5988: 5983: 5979: 5978:← 2 5975: 5972: 5968: 5964: 5960: 5957: 5953: 5949: 5945: 5941: 5937: 5933: 5929: 5926: 5922: 5918: 5915: 5909: 5905: 5901: 5897: 5890: 5884: 5878: 5872: 5865: 5859: 5853: 5847: 5841: 5834: 5827: 5820: 5816: 5758: 5751: 5747: 5743: 5682: 5676: 5670: 5664: 5658: 5654: 5647: 5641: 5635: 5629: 5623: 5622:with digits 5615: 5608:Bit reversal 5604:bit reversal 5603: 5601: 5593: 5583: 5579: 5575: 5569: 5562: 5554: 5550: 5546: 5542: 5537: 5533: 5529: 5525: 5521: 5517: 5513: 5509: 5502: 5496: 5492: 5488: 5481: 5477: 5470: 5466: 5458: 5454: 5450: 5445: 5441: 5437: 5433: 5429: 5425: 5423: 5415: 5408: 5406: 4383: 4376:column-major 4368: 4361: 4357: 4353: 4349: 4342: 4341:run from 0.. 4335: 4328: 4212: 4208: 4206: 4193: 4183: 4169: 4162: 4158: 4156: 4152:CPU pipeline 4130: 4126: 4122: 4118: 4116: 4098: 4094: 4087: 4083: 4076: 4072: 4068: 4061: 4054: 4052: 4043: 4036: 4015: 4008: 3997: 3991: 3987: 3985: 3976: 3969: 3958: 3951: 3944: 3938: 3934: 3847: 3845: 3836: 3834: 3826: 3822: 3818: 3811: 3803: 3799: 3796:out-of-place 3791: 3787: 3783: 3779: 3774: 3771: 3767: 3764: 3758: 3750: 3743: 3738: 3730: 3726: 3723: 3719: 3712: 3708: 3705: 3701: 3697: 3694: 3689: 3685: 3680: 3675: 3667: 3662: 3654: 3647: 3646:) 3643: 3639: 3635: 3631: 3625: 3617: 3612: 3608: 3603: 3598: 3593: 3588: 3583: 3576: 3572: 3568: 3564: 3560: 3554: 3549: 3546: 3543: 3537: 3530: 3527: 3523: 3520: 3515: 3511: 3506: 3501: 3496: 3489: 3482: 3478: 3474: 3470: 3466: 3460: 3455: 3447: 3414:linearithmic 3409: 3392: 3388: 3384: 3382: 3371: 3365: 3361: 3357: 3353: 3249: 3245: 3243: 2982: 1801: 1173: 1172: 1110: 1109: 966: 626: 621: 618:power of two 613: 609: 605: 419: 370: 260: 255: 251: 247: 243: 241: 216: 198:Soviet Union 191: 175:James Cooley 153: 141: 122: 113: 109: 105: 94: 87: 86:in terms of 25:J. W. Cooley 20: 18: 6784:(1): 1–26. 6778:SIAM Review 6723:at Citeseer 6677:Proc. AFIPS 6514:Commun. ACM 6223:depth-first 5995:) 5612:permutation 4198:out-of-core 4143:Split radix 4119:Mixed-radix 3911:depth-first 3718:q ← exp(−2π 3430:real inputs 602:recursively 129:Bluestein's 102:recursively 7246:Categories 6916:Proc. IEEE 6451:Proc. IEEE 6436:2009-03-31 6241:References 5528: log( 4177:transposed 4113:Variations 3806:=1 is the 3693:) 3616:) 3450:pseudocode 3444:Pseudocode 220:I. J. Good 183:John Tukey 29:John Tukey 7183:"KISSFFT" 7151:121258187 7129:CiteSeerX 6827:CiteSeerX 6786:CiteSeerX 6638:CiteSeerX 6569:Computing 6419:SIAM News 6371:CiteSeerX 6176: := 6110:algorithm 5987:← exp(−2π 5923:algorithm 5540: log 5461: log 5448: log 5310:π 5301:− 5250:π 5241:− 5188:− 5156:∑ 5142:− 5110:∑ 5047:π 5038:− 4987:π 4978:− 4925:− 4893:∑ 4830:π 4821:− 4804:− 4772:∑ 4706:⋅ 4664:⋅ 4633:π 4624:− 4571:− 4539:∑ 4530:− 4498:∑ 4139:Bluestein 4103:butterfly 4099:butterfly 3876:π 3870:− 3864:⁡ 3648:DFT of (x 3577:DFT of (x 3483:DFT of (x 3394:Danielson 3380:fashion. 3343:butterfly 3312:π 3306:− 3300:⁡ 3199:π 3190:− 3182:− 3109:π 3100:− 2940:π 2931:− 2923:− 2873:π 2864:− 2832:− 2806:∑ 2788:π 2779:− 2771:− 2741:π 2732:− 2706:− 2680:∑ 2658:π 2652:− 2617:π 2608:− 2576:− 2550:∑ 2541:π 2538:− 2516:π 2507:− 2488:π 2482:− 2447:π 2438:− 2412:− 2386:∑ 2326:π 2317:− 2285:− 2259:∑ 2222:π 2213:− 2156:π 2147:− 2121:− 2095:∑ 1936:− 1920:… 1831:− 1822:… 1780:− 1764:… 1719:π 1710:− 1631:− 1598:⏟ 1567:π 1558:− 1526:− 1500:∑ 1478:π 1469:− 1401:− 1365:⏟ 1334:π 1325:− 1299:− 1273:∑ 989:π 980:− 916:π 907:− 875:− 849:∑ 816:π 807:− 781:− 755:∑ 580:− 566:… 487:− 473:… 402:− 336:π 327:− 304:− 286:∑ 187:Princeton 171:Neo-Latin 160:asteroids 139:factors. 41:composite 7028:A free ( 7009:14610645 6894:62201722 6859:14307262 6262:Nachlass 6256:(1866). 6143:of size 5436:to be O( 4348:-1 (for 4194:six-step 4035:Perform 4007:Perform 3434:IBM 7094 3410:doubling 208:helium-3 7094:Bibcode 6808:2132972 6660:6644892 6630:Bibcode 6536:6287781 6453:, vol. 6341:2003354 6137:output: 5942:output: 5610:is the 5567:√ 5532:) 5469:) 4181:√ 3775:ditfft2 3765:end for 3700:= 0 to 3679:, ..., 3632:ditfft2 3624:/2,..., 3602:, ..., 3561:ditfft2 3519:): 3505:, ..., 3467:ditfft2 3406:Runge's 3398:Lanczos 244:radix-2 196:in the 150:History 125:Rader's 7201:GitHub 7197:Dsplib 7187:GitHub 7149: 7131: 7024:"FFTW" 7007: 6987:J. ACM 6964: 6908:et al. 6892: 6857: 6847: 6829: 6806: 6788: 6759: 6658: 6640: 6534: 6491:," in 6373: 6339: 6237:data. 6147:. 6139:Array 6127:Array 6125:input: 6099:return 5944:Array 5932:Array 5930:input: 5744:halves 5620:binary 5457:) = O( 5440: 4386:, the 4137:'s or 3957:× 3808:stride 3772:Here, 3768:end if 3553:0,..., 3459:0,..., 371:where 163:Pallas 7147:S2CID 7005:S2CID 6958:51–83 6890:S2CID 6855:S2CID 6804:JSTOR 6656:S2CID 6618:(PDF) 6532:S2CID 6430:(PDF) 6415:(PDF) 6359:(PDF) 6337:JSTOR 6211:Pease 5910:input 5817:least 5757:(for 4360:) as 4148:cache 4135:Rader 4073:radix 3907:cache 3815:array 3790:=DFT( 3704:/2−1 3642:/2, 2 3571:/2, 2 3402:lemma 616:is a 43:size 6962:ISBN 6845:ISBN 6757:ISBN 6217:log 6207:SIMD 6169:– 1 6162:= 0 6040:– 1 6029:= 0 6002:= 0 5967:log( 5963:= 1 5788:and 5748:most 5715:and 5516:log 5505:/log 5484:/log 5473:/log 4378:and 4334:and 4271:and 4211:and 4150:and 4003:as: 3925:Idea 3711:p ← 3638:+s, 3557:/2−1 3547:else 3528:then 3526:= 1 3279:and 3050:as: 3010:and 2022:and 1873:and 608:log 181:and 167:Juno 165:and 108:log 27:and 19:The 7199:on 7139:doi 7102:doi 7067:doi 7030:GPL 6995:doi 6882:doi 6837:doi 6796:doi 6648:doi 6587:," 6522:doi 6471:233 6381:doi 6327:doi 6289:, " 6157:for 6131:of 6024:for 6009:-1 5997:for 5958:for 5936:of 5898:all 4367:by 4215:as 4168:by 4069:not 4060:or 3861:exp 3817:. 3695:for 3688:-1) 3611:-2) 3514:-1) 3448:In 3297:exp 1213:by 1144:by 248:DIT 185:of 179:IBM 177:of 127:or 7248:: 7185:. 7170:. 7145:. 7137:. 7125:68 7123:. 7100:. 7090:52 7088:. 7063:12 7061:. 7003:. 6991:15 6989:. 6985:. 6960:. 6934:, 6923:^ 6914:, 6910:, 6888:. 6878:16 6876:. 6853:. 6843:. 6835:. 6802:. 6794:. 6782:38 6780:. 6739:12 6721:, 6706:^ 6687:^ 6680:29 6668:^ 6654:. 6646:. 6636:. 6626:93 6624:. 6620:. 6599:^ 6592:55 6572:80 6556:19 6544:^ 6530:. 6518:10 6516:. 6512:. 6500:^ 6478:^ 6455:55 6423:33 6421:. 6417:. 6379:. 6367:15 6365:. 6361:. 6335:. 6323:19 6316:. 6298:^ 6270:^ 6233:. 6171:do 6164:to 6151:← 6122:is 6120:) 6086:← 6079:– 6075:← 6068:+ 6064:← 6057:← 6047:← 6042:do 6031:to 6017:do 6011:by 6004:to 5973:do 5971:) 5965:to 5952:← 5927:is 5902:or 4384:nk 4204:. 4032:). 3990:= 3937:= 3832:. 3794:) 3761:/2 3741:/2 3729:) 3706:do 3674:+4 3666:, 3661:+2 3653:, 3630:← 3628:−1 3592:, 3582:, 3567:, 3559:← 3536:← 3521:if 3495:, 3488:, 3477:, 3473:, 3465:← 3463:−1 2049:: 1955:, 1783:1. 722:: 417:. 242:A 100:, 7153:. 7141:: 7108:. 7104:: 7096:: 7073:. 7069:: 7026:. 7011:. 6997:: 6970:. 6896:. 6884:: 6861:. 6839:: 6810:. 6798:: 6765:. 6725:. 6699:4 6662:. 6650:: 6632:: 6538:. 6524:: 6439:. 6402:2 6387:. 6383:: 6343:. 6329:: 6219:N 6215:N 6188:N 6178:a 6174:A 6167:n 6160:k 6153:a 6149:n 6145:n 6141:A 6133:n 6129:a 6118:A 6116:, 6114:a 6102:A 6095:m 6091:ω 6088:ω 6084:ω 6081:t 6077:u 6073:A 6070:t 6066:u 6062:A 6059:A 6055:u 6052:A 6049:ω 6045:t 6038:2 6036:/ 6034:m 6027:j 6020:ω 6014:m 6007:n 6000:k 5993:m 5991:/ 5989:i 5984:m 5980:ω 5976:m 5969:n 5961:s 5954:a 5950:n 5946:A 5938:n 5934:a 5906:N 5894:2 5891:b 5888:3 5885:b 5882:4 5879:b 5876:1 5873:b 5869:1 5866:b 5863:2 5860:b 5857:3 5854:b 5851:4 5848:b 5845:0 5842:b 5838:4 5835:b 5831:0 5828:b 5824:0 5821:b 5801:k 5797:O 5774:k 5770:E 5759:N 5755:4 5752:b 5728:k 5724:O 5701:k 5697:E 5686:4 5683:b 5680:3 5677:b 5674:2 5671:b 5668:1 5665:b 5662:0 5659:b 5655:N 5651:0 5648:b 5645:1 5642:b 5639:2 5636:b 5633:3 5630:b 5627:4 5624:b 5616:n 5584:N 5580:N 5576:N 5570:N 5565:= 5563:r 5555:r 5551:r 5547:N 5543:r 5538:r 5536:/ 5534:N 5530:r 5526:r 5522:r 5518:r 5514:r 5510:r 5507:2 5503:r 5498:e 5493:r 5489:r 5486:2 5482:r 5478:r 5475:2 5471:r 5467:N 5465:( 5463:2 5459:N 5455:N 5451:r 5446:r 5444:/ 5442:N 5438:r 5434:r 5430:r 5426:r 5419:1 5416:N 5412:2 5409:N 5401:. 5387:) 5382:2 5378:k 5374:+ 5369:1 5365:k 5359:2 5355:N 5351:( 5346:1 5342:n 5333:2 5329:N 5323:1 5319:N 5313:i 5307:2 5297:e 5292:) 5284:2 5280:k 5274:2 5270:n 5262:2 5258:N 5253:i 5247:2 5237:e 5229:1 5225:n 5221:+ 5216:2 5212:n 5206:1 5202:N 5197:x 5191:1 5183:2 5179:N 5173:0 5170:= 5165:2 5161:n 5151:( 5145:1 5137:1 5133:N 5127:0 5124:= 5119:1 5115:n 5106:= 5081:1 5077:k 5071:1 5067:n 5059:1 5055:N 5050:i 5044:2 5034:e 5029:) 5021:2 5017:k 5011:2 5007:n 4999:2 4995:N 4990:i 4984:2 4974:e 4966:1 4962:n 4958:+ 4953:2 4949:n 4943:1 4939:N 4934:x 4928:1 4920:2 4916:N 4910:0 4907:= 4902:2 4898:n 4888:( 4883:] 4876:2 4872:k 4866:1 4862:n 4853:2 4849:N 4843:1 4839:N 4833:i 4827:2 4817:e 4813:[ 4807:1 4799:1 4795:N 4789:0 4786:= 4781:1 4777:n 4768:= 4745:) 4740:2 4736:k 4732:+ 4727:1 4723:k 4717:2 4713:N 4709:( 4703:) 4698:1 4694:n 4690:+ 4685:2 4681:n 4675:1 4671:N 4667:( 4656:2 4652:N 4646:1 4642:N 4636:i 4630:2 4620:e 4612:1 4608:n 4604:+ 4599:2 4595:n 4589:1 4585:N 4580:x 4574:1 4566:2 4562:N 4556:0 4553:= 4548:2 4544:n 4533:1 4525:1 4521:N 4515:0 4512:= 4507:1 4503:n 4494:= 4487:2 4483:k 4479:+ 4474:1 4470:k 4464:2 4460:N 4455:X 4429:1 4425:k 4419:2 4415:N 4409:2 4405:n 4399:1 4395:N 4372:2 4369:N 4365:1 4362:N 4358:k 4354:n 4350:a 4346:a 4343:N 4339:a 4336:n 4332:a 4329:k 4313:1 4309:n 4305:+ 4300:2 4296:n 4290:1 4286:N 4282:= 4279:n 4257:2 4253:k 4249:+ 4244:1 4240:k 4234:2 4230:N 4226:= 4223:k 4213:n 4209:k 4184:N 4173:2 4170:N 4166:1 4163:N 4159:N 4131:N 4127:N 4123:N 4091:2 4088:N 4080:1 4077:N 4065:2 4062:N 4058:1 4055:N 4049:. 4047:1 4044:N 4040:2 4037:N 4021:. 4019:2 4016:N 4012:1 4009:N 4001:2 3998:N 3995:1 3992:N 3988:N 3980:1 3977:N 3973:2 3970:N 3962:2 3959:N 3955:1 3952:N 3948:2 3945:N 3942:1 3939:N 3935:N 3893:] 3890:N 3886:/ 3882:k 3879:i 3873:2 3867:[ 3848:N 3837:X 3829:s 3827:x 3823:s 3821:+ 3819:x 3812:x 3804:s 3800:N 3792:x 3788:X 3784:N 3782:, 3780:x 3778:( 3759:N 3757:+ 3753:k 3751:X 3746:k 3744:X 3739:N 3737:+ 3733:k 3731:X 3727:k 3724:N 3722:/ 3720:i 3715:k 3713:X 3702:N 3698:k 3690:s 3686:N 3684:( 3681:x 3676:s 3670:s 3668:x 3663:s 3657:s 3655:x 3650:s 3644:s 3640:N 3636:x 3634:( 3626:N 3620:N 3618:X 3613:s 3609:N 3607:( 3604:x 3599:s 3597:4 3594:x 3589:s 3587:2 3584:x 3580:0 3573:s 3569:N 3565:x 3563:( 3555:N 3550:X 3541:0 3538:x 3534:0 3531:X 3524:N 3516:s 3512:N 3510:( 3507:x 3502:s 3500:2 3497:x 3492:s 3490:x 3486:0 3479:s 3475:N 3471:x 3469:( 3461:N 3456:X 3396:– 3389:N 3385:N 3366:N 3362:N 3358:N 3354:N 3329:) 3326:N 3322:/ 3318:k 3315:i 3309:2 3303:( 3292:k 3288:O 3265:k 3261:E 3250:N 3246:N 3223:k 3219:O 3212:k 3206:N 3202:i 3196:2 3186:e 3177:k 3173:E 3167:= 3158:2 3155:N 3150:+ 3147:k 3143:X 3133:k 3129:O 3122:k 3116:N 3112:i 3106:2 3096:e 3092:+ 3087:k 3083:E 3077:= 3070:k 3066:X 3034:2 3031:N 3026:+ 3023:k 3019:X 2996:k 2992:X 2962:k 2958:O 2952:k 2947:N 2943:i 2937:2 2927:e 2918:k 2914:E 2910:= 2898:k 2895:m 2889:2 2885:/ 2881:N 2876:i 2870:2 2860:e 2854:1 2851:+ 2848:m 2845:2 2841:x 2835:1 2829:2 2825:/ 2821:N 2816:0 2813:= 2810:m 2800:k 2795:N 2791:i 2785:2 2775:e 2766:k 2763:m 2757:2 2753:/ 2749:N 2744:i 2738:2 2728:e 2722:m 2719:2 2715:x 2709:1 2703:2 2699:/ 2695:N 2690:0 2687:= 2684:m 2676:= 2664:i 2661:m 2655:2 2648:e 2642:k 2639:m 2633:2 2629:/ 2625:N 2620:i 2614:2 2604:e 2598:1 2595:+ 2592:m 2589:2 2585:x 2579:1 2573:2 2569:/ 2565:N 2560:0 2557:= 2554:m 2544:i 2534:e 2528:k 2523:N 2519:i 2513:2 2503:e 2499:+ 2494:i 2491:m 2485:2 2478:e 2472:k 2469:m 2463:2 2459:/ 2455:N 2450:i 2444:2 2434:e 2428:m 2425:2 2421:x 2415:1 2409:2 2405:/ 2401:N 2396:0 2393:= 2390:m 2382:= 2370:) 2365:2 2362:N 2357:+ 2354:k 2351:( 2348:m 2342:2 2338:/ 2334:N 2329:i 2323:2 2313:e 2307:1 2304:+ 2301:m 2298:2 2294:x 2288:1 2282:2 2278:/ 2274:N 2269:0 2266:= 2263:m 2253:) 2248:2 2245:N 2240:+ 2237:k 2234:( 2229:N 2225:i 2219:2 2209:e 2205:+ 2200:) 2195:2 2192:N 2187:+ 2184:k 2181:( 2178:m 2172:2 2168:/ 2164:N 2159:i 2153:2 2143:e 2137:m 2134:2 2130:x 2124:1 2118:2 2114:/ 2110:N 2105:0 2102:= 2099:m 2091:= 2080:2 2077:N 2072:+ 2069:k 2065:X 2035:k 2031:O 2008:k 2004:E 1979:2 1976:N 1971:+ 1968:k 1964:X 1939:1 1931:2 1928:N 1923:, 1917:, 1914:0 1911:= 1908:k 1886:k 1882:O 1859:k 1855:E 1834:1 1828:N 1825:, 1819:, 1816:0 1813:= 1810:k 1775:2 1772:N 1767:, 1761:, 1758:0 1755:= 1752:k 1741:k 1737:O 1731:k 1726:N 1722:i 1716:2 1706:e 1702:+ 1697:k 1693:E 1689:= 1682:n 1678:x 1672:f 1669:o 1665:t 1662:r 1659:a 1656:p 1652:d 1649:e 1646:x 1643:e 1640:d 1637:n 1634:i 1628:d 1625:d 1622:o 1618:f 1615:o 1611:T 1608:F 1605:D 1592:k 1589:m 1583:2 1579:/ 1575:N 1570:i 1564:2 1554:e 1548:1 1545:+ 1542:m 1539:2 1535:x 1529:1 1523:2 1519:/ 1515:N 1510:0 1507:= 1504:m 1490:k 1485:N 1481:i 1475:2 1465:e 1461:+ 1452:n 1448:x 1442:f 1439:o 1435:t 1432:r 1429:a 1426:p 1422:d 1419:e 1416:x 1413:e 1410:d 1407:n 1404:i 1398:n 1395:e 1392:v 1389:e 1385:f 1382:o 1378:T 1375:F 1372:D 1359:k 1356:m 1350:2 1346:/ 1342:N 1337:i 1331:2 1321:e 1315:m 1312:2 1308:x 1302:1 1296:2 1292:/ 1288:N 1283:0 1280:= 1277:m 1265:= 1260:k 1256:X 1226:k 1222:O 1199:1 1196:+ 1193:m 1190:2 1186:x 1174:O 1157:k 1153:E 1130:m 1127:2 1123:x 1111:E 1094:n 1090:x 1067:1 1064:+ 1061:m 1058:2 1054:x 1031:m 1028:2 1024:x 1001:k 996:N 992:i 986:2 976:e 946:k 943:) 940:1 937:+ 934:m 931:2 928:( 923:N 919:i 913:2 903:e 897:1 894:+ 891:m 888:2 884:x 878:1 872:2 868:/ 864:N 859:0 856:= 853:m 845:+ 840:k 837:) 834:m 831:2 828:( 823:N 819:i 813:2 803:e 797:m 794:2 790:x 784:1 778:2 774:/ 770:N 765:0 762:= 759:m 749:= 742:k 738:X 709:1 706:+ 703:m 700:2 696:= 693:n 672:m 669:2 665:= 662:n 640:n 636:x 622:N 614:N 610:N 606:N 588:) 583:1 577:N 573:x 569:, 563:, 558:3 554:x 550:, 545:1 541:x 537:= 532:1 529:+ 526:m 523:2 519:x 515:( 495:) 490:2 484:N 480:x 476:, 470:, 465:2 461:x 457:, 452:0 448:x 444:= 439:m 436:2 432:x 428:( 405:1 399:N 379:k 356:, 351:k 348:n 343:N 339:i 333:2 323:e 317:n 313:x 307:1 301:N 296:0 293:= 290:n 282:= 277:k 273:X 256:N 252:N 116:( 114:N 110:N 106:N 98:2 95:N 91:1 88:N 72:2 68:N 62:1 58:N 54:= 51:N

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge (XXG)

Cooley–Tukey FFT algorithm

Index