Metraipolis › archive › dc_cd47ef35d51f

Cooley–Tukey FFT algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T21:28:04.898Z
SHA-256 of the archived text
d1b09927e121d4018b8430f3b0198cd472307aa65a35887bd75916d68884f0ff
Stable URL of this page
https://metraipolis.com/documento/dc_cd47ef35d51f

How to cite

Cooley–Tukey FFT algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cd47ef35d51f (Metraipolis archive dc_cd47ef35d51f, sha256 d1b09927e121d4018b8430f3b0198cd472307aa65a35887bd75916d68884f0ff)
BibTeX
@misc{dccd47ef35d51f,
  title = {Cooley–Tukey FFT algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cd47ef35d51f; sha256 d1b09927e121d4018b8430f3b0198cd472307aa65a35887bd75916d68884f0ff},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 {\displaystyle N=N_{1}N_{2}} in terms of N1 smaller DFTs of sizes N2, recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. 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, Rader's or Bluestein's algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the prime-factor algorithm can be exploited for greater efficiency in separating out relatively prime factors. The algorithm, along with its recursive application, was invented by Carl Friedrich Gauss. Cooley and Tukey independently rediscovered and popularized it 160 years later.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Cooley–Tukey FFT algorithm» — https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
Wikidata Q5167446 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5167446
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1373740970, consultata il 2026-10-07T21:00:20.324Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 21bdaa3ea64ce495f4dba2a173ce4b7036b121e0ae27210196194aa24c9eb576