A twiddle factor, in

fast Fourier transform 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 th ...

(FFT) algorithms, is any of the

trigonometric Trigonometry () is a branch of mathematics that studies relationships between side lengths and angles of triangles. The field emerged in the Hellenistic world during the 3rd century BC from applications of geometry to astronomical studies. ...

constant coefficients that are multiplied by the data in the course of the algorithm. This term was apparently coined by Gentleman & Sande in 1966, and has since become widespread in thousands of papers of the FFT literature. More specifically, "twiddle factors" originally referred to the root-of-unity

complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...

multiplicative constants in the

butterfly Butterflies are insects in the macrolepidopteran clade Rhopalocera from the Order (biology), order Lepidoptera, which also includes moths. Adult butterflies have large, often brightly coloured wings, and conspicuous, fluttering flight. The ...

operations of the

Cooley–Tukey FFT algorithm 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_1N_2 in terms of ''N''1 ...

, used to

recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...

combine smaller

discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex- ...

s. This remains the term's most common meaning, but it may also be used for any data-independent multiplicative constant in an FFT. The

prime-factor FFT algorithm The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size ''N'' = ''N''1''N''2 as a two-dimensional ''N''1× ...

is one unusual case in which an FFT can be performed without twiddle factors, albeit only for restricted factorizations of the transform size. For example, W₈² is a twiddle factor used in 8-point radix-2 FFT.

References

* W. M. Gentleman and G. Sande, "Fast Fourier transforms—for fun and profit," ''Proc. AFIPS'' 29, 563–578 (1966). {{doi, 10.1145/1464291.1464352 FFT algorithms