# Fast Fourier transform <!-- MICROSIMGEN:BEGIN v1.7 — generated by g08_place_microsims.py; three.js first (§15); do not hand-edit inside --> ## Microsims — p5.js ### Fast Fourier transform (p5.js) · `O(N log N)` <div class="microsim-player"> <iframe src="https://editor.p5js.org/sciencenibber/full/UBIUlq_4m" width="100%" height="480" frameborder="0" loading="lazy" sandbox="allow-scripts allow-same-origin" title="Fast Fourier transform — p5.js microsim"></iframe> </div> *The algorithm that computes the DFT in N log N instead of N² steps — arguably the most important algorithm in DSP.* **Open in the editor:** [&#9654; fork this sketch](https://editor.p5js.org/sciencenibber/sketches/UBIUlq_4m) · movement *II · Transforms & the frequency domain* · library `p5js` ### Related microsims Live sims on neighbouring articles — 6 of them inside this article's own Wikipedia link tree: - [[Convolution]] *(in tree)* - [[Digital_signal_processing]] *(in tree)* - [[Discrete_cosine_transform]] *(in tree)* - [[Discrete_wavelet_transform]] *(in tree)* - [[Frequency_domain]] *(in tree)* - [[Least-squares_spectral_analysis]] *(in tree)* *Sim hosted off-article; the article owns the reference, not the runtime (WIKI_RULES §10.4). Placed by `g08_place_microsims.py`.* <!-- MICROSIMGEN:END --> ## Links (Wikipedia order) <!-- injected from _registry/childlinks/Fast_Fourier_transform.json (2026-07-30T02:09:12Z) --> `2_Pallas` · `3_Juno` · `5G_NR` · `ALGLIB` · `Academic_Press` · `Additive_synthesis` · `Advances_in_Mathematics` · [[Algorithm]] · `American_Scientist` · `Arm` · `Birkhäuser` · `Bit-reversal_permutation` · `Brian_P._Flannery` · `Bruun's_FFT_algorithm` · `Butterfly_diagram` · `C++` · `CRC_Press` · `C_(programming_language)` · `Cache-oblivious_algorithm` · `Cache_(computing)` · `Cambridge_University_Press` · `Carl_Friedrich_Gauss` · `Central_processing_unit` · `Charles_E._Leiserson` · `Chinese_remainder_theorem` · `Chirp_Z-transform` · `Christos_Papadimitriou` · `Clifford_Stein` · `Complex_number` · `Composite_number` · `Computational_complexity` · `Computational_complexity_theory` · `Computing_(journal)` · [[Convolution]] · `Convolution_theorem` · `Cooley–Tukey_FFT_algorithm` · `Coordinate_vector` · `Cornelius_Lanczos` · `Cyclotomic_polynomial` · `DFT_matrix` · [[Digital_signal_processing]] · `Dirichlet_series` · `Discrete-time_Fourier_transform` · `Discrete_Fourier_transform` · `Discrete_Hartley_transform` · [[Discrete_cosine_transform]] · `Discrete_sine_transform` · [[Discrete_wavelet_transform]] · `Distributed_memory` · `Divide-and-conquer_algorithm` · `Douglas_L._Jones` · `Electronics_Letters` · `Even_and_odd_functions` · `FFTPACK` · `FFT_(disambiguation)` · `Factorization` · `Fast_Algorithms_for_Multidimensional_Signals` · `Fast_Walsh–Hadamard_transform` · `Fast_folding_algorithm` · `Fast_multipole_method` · `Fastest_Fourier_Transform_in_the_West` · `Finite_field` · `Fixed-point_arithmetic` · `Floating-point_unit` · `Fortran` · `Fourier_transform` · `Fourier_transform_on_finite_groups` · `Frank_Yates` · [[Frequency_domain]] · `Funda_Ergun` · `G._C._Danielson` · `GNU_Octave` · `Gabriele_Steidl` · `Generalized_distributive_law` · `Generating_set_of_a_group` · `Gilbert_Strang` · `Goertzel_algorithm` · `Graph_(discrete_mathematics)` · `Group_(mathematics)` · `Group_theory` · `Haskell` · `Hexagonal_fast_Fourier_transform` · `I._J._Good` · `Information_Processing_Letters` · `Integer_factorization` · `Introduction_to_Algorithms` · `JPEG` · `John_Tukey` · `Joseph_Fourier` · `Journal_of_the_ACM` · `Julia_(programming_language)` · `K._R._Rao` · `LIGO` · [[Least-squares_spectral_analysis]] · `List_of_unsolved_problems_in_computer_science` · `MATLAB` · `MIT_Press` · `MP3` · `Mass_spectrometry` · `Math_Kernel_Library` · `Mathematics_of_Computation` · `Matrix_(mathematics)` · `Matrix_decomposition` · `Multidimensional_discrete_convolution` · `Multidimensional_transform` · `Multiplication_algorithm` · `Non-uniform_discrete_Fourier_transform` · `Number_theory` · `Numerical_Recipes` · `Numerical_stability` · `Odlyzko–Schönhage_algorithm` · `Orthogonal_frequency-division_multiplexing` · `Overlap–add_method` · `Overlap–save_method` · `Pairwise_summation` · `Parallel_computing` · `Piotr_Indyk` · `Polynomial` · `Power_of_two` · `Prime-factor_FFT_algorithm` · `Proceedings_of_SPIE` · `Proceedings_of_the_IEEE` · `Proof_by_exhaustion` · `Python_(programming_language)` · `Quantum_Fourier_transform` · `R_(programming_language)` · `Rader's_FFT_algorithm` · [[Recurrence_relation]] · `Richard_Garwin` · `Root_mean_square` · `Round-off_error` · `Rust_(programming_language)` · `SIAM_Journal_on_Scientific_Computing` · `Satisfiability_modulo_theories` · `Saul_Teukolsky` · `Schönhage–Strassen_algorithm` · `Scilab` · [[Sequence]] · `Short-time_Fourier_transform` · `Society_for_Industrial_and_Applied_Mathematics` · `Sparse_matrix` · `Spectral_music` · `Spectrum_analyzer` · `Spherical_harmonics` · `Springer_Science+Business_Media` · `Thomas_H._Cormen` · `Thomas_J._Watson_Research_Center` · [[Time_domain]] · [[Time_series]] · `Toeplitz_matrix` · `Transpose` · `Wavelet` · [[Wayback_Machine]] · `William_H._Press` · `X-ray_crystallography` > Signal Processing concept · part of the Signal Processing Portal · movement II · !31 変換 henkan.svg <!-- RENDER-THUMB:START --> !480 *Rendered from the live microsim (▶ motion).* <!-- RENDER-THUMB:END --> ## See it next [](Discrete_Fourier_transform) *→ Discrete Fourier transform* <!-- VISUAL-LINK:END --> --- Back to Signal Processing Portal · the room · Semiotic gateway <!-- REAL-GENERATIVE-MEDIA:START --> ## What it is The fast Fourier transform is any algorithm that computes the discrete Fourier transform (and its inverse) in O(N log N) operations instead of the O(N^2) required by direct evaluation. ## How it works / why it matters The classic Cooley-Tukey algorithm uses divide-and-conquer, recursively splitting an N-point DFT into smaller DFTs (for example even- and odd-indexed samples) and recombining them with twiddle factors. This dramatic speedup made real-time spectral analysis practical and turned the DFT into the workhorse of modern digital signal processing, from spectrum analyzers to fast convolution. ## Signs & universals Instantiates: transformation, frequency, spectrum. ## Related See Discrete Fourier transform, Discrete-time Fourier transform, Fourier transform, Goertzel algorithm, [[Discrete_cosine_transform]], and [[Fourier_analysis]]. <!-- VISUAL-LINK:START --> ## From the Real GENERATIVE library > A fast Fourier transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. ([Wikipedia](https://en.wikipedia.org/wiki/Fast_Fourier_transform)) <!-- REAL-GENERATIVE-MEDIA:END --> <!-- CRAFT-LINK:START g12 --> *Built to the [[WT!P5_js_Microsim_Master_Class|p5.js Master Class]].* <!-- CRAFT-LINK:END --> ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Fast_Fourier_transform) : [Wikitube](https://en.wikitube.io/wiki/Fast_Fourier_transform) ## Previous hub tags Tree parent: [[Information_theory]]. Legacy hubs: none. --- *Sources: 1 legacy note. Minted wave 1, 2026-07-30 (v1.6 order).*