Fast Fourier Transform
Prerequisite reading: complex numbers.
This article presents an algorithm that multiplies two polynomials of degree \(n\) in \(O(n\log n)\) time, faster than the naive \(O(n^2)\) algorithm. Multiplying two integers can also be viewed as multiplying two polynomials, so the same algorithm speeds up the multiplication of big integers.
Introduction
Take two polynomials \(A\) and \(B\):
Their product \(C = A \times B\) can be computed in \(O(n^2)\) time (here \(n\) is the degree of \(A\) or \(B\)):
Clearly, the coefficients \(c_i\) of \(C\) satisfy \(c_i = \sum_{j = 0}^i a_j b_{i - j}\). The naive algorithm spends \(O(n)\) time on each coefficient, and there are \(O(n)\) of them, so its time complexity is \(O(n^2)\).
Can we do better? With the fast Fourier transform, the complexity drops to \(O(n \log n)\).
Fourier transform
The Fourier transform is a method for analyzing signals: it breaks a signal down into its components, and it can also synthesize a signal from those components. Many waveforms could serve as the components; the Fourier transform uses sine waves.
Let \(f(t)\) be a function of time \(t\). The Fourier transform measures how strongly a periodic component of frequency \(\omega\) is present in \(f(t)\):
Its inverse transform is
The inverse transform looks very much like the forward transform; the denominator \(2\pi\) is exactly the period of the exponential function.
The Fourier transform amounts to a continuous inner product of the time-domain function with a complex exponential function of period \(2\pi\). The inverse transform is again an inner product.
The Fourier transform comes with a convolution theorem: a convolution in the time domain becomes a product in the frequency domain, and a convolution in the frequency domain becomes a product in the time domain.
Discrete Fourier transform
The discrete Fourier transform (DFT) is the form of the Fourier transform that is discrete in both the time domain and the frequency domain. It turns time-domain samples of a signal into frequency-domain samples of its discrete-time Fourier transform (DTFT).
The Fourier transform is a continuous inner product of functions, written as an integral; the discrete Fourier transform is an inner product written as a sum.
Let \(\{x_n\}_{n=0}^{N-1}\) be a finite sequence. Its discrete Fourier transform (DFT) is:
where \(\mathrm{e}\) is the base of the natural logarithm and \(i\) is the imaginary unit. The transform is usually denoted by the symbol \(\mathcal {F}\), that is,
As with the integral form, its inverse discrete Fourier transform (IDFT) is:
which can be written as:
The normalization factors in front of the sums in the DFT and the IDFT do not really matter. In the definitions above they are \(1\) and \(\frac {1}{N}\) respectively. Sometimes both are changed to \(\frac{1}{{\sqrt{N}}}\).
The discrete Fourier transform is still a transform from the time domain to the frequency domain. But because it is a sum, it can be interpreted in other ways as well.
If we regard \(x_n\) as the coefficient of \(x^n\) in a polynomial \(f(x)\), then \(X_k\) is exactly the point value \(f(\mathrm{e}^{\frac{-2\pi \mathrm{i}k}{N}})\) of \(f(x)\) at the root of unity \(\mathrm{e}^{\frac{-2\pi \mathrm{i}k}{N}}\).
This gives another way to read the convolution theorem: as a special kind of polynomial evaluation. The discrete Fourier transform is exactly the evaluation of a polynomial at the roots of unity.
For example, suppose we want to compute:
Define the function \(f(x)\) as:
Evaluating it at a fourth root of unity gives \(f(\mathrm{i})\), which expands to:
The following sum then cancels all the other terms:
So the answer to this problem is:
The problem is solved by evaluating at the roots of unity, which is exactly a discrete Fourier transform.
Matrix form
The discrete Fourier transform is a linear operator, so it can be described by a matrix multiplication. In matrix notation it reads:
where \(\alpha = \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}}\).
Fast Fourier transform
The fast Fourier transform (FFT) is an algorithm that computes the DFT efficiently. It added nothing new to the theory of the Fourier transform, but it was a big step forward for applying the discrete Fourier transform in computer systems, or digital systems in general. The number theoretic transform (NTT) is the FFT carried out in a number-theoretic setting.
Cooley and Tukey published the fast Fourier transform algorithm in 1965. The FFT had actually been discovered earlier, but modern computers did not exist yet and nobody realized how important it was. Some researchers attribute the discovery of the FFT to Runge and König in 1924. In fact, Gauss had already invented the algorithm in 1805 but never published it.
Implementation by divide and conquer
The basic idea of the FFT is divide and conquer. For the DFT, it computes the values of \(f(x)\) at \(x=\omega_n^k\) by divide and conquer. The radix-2 FFT divides the polynomial into its odd-degree terms and its even-degree terms.
For example, take a polynomial with \(8\) terms:
Split the terms into two groups by the parity of their degree, and factor an \(x\) out of the right-hand group:
Build two new functions, one from the even-degree coefficients and one from the odd-degree coefficients:
The original \(f(x)\) can then be written in terms of them:
Roots of unity of even order satisfy \(\omega^i_n = -\omega^{i + n/2}_n\), and \(G\left(x^2\right)\) and \(H\left(x^2\right)\) are even functions. So at the points \(\omega^i_n\) and \(\omega^{i+n/2}_n\) of the complex plane, \(G(x^2)\) and \(H(x^2)\) take the same values. This gives:
and:
So once we have \(G(\omega_{n/2}^k)\) and \(H(\omega_{n/2}^k)\), we get both \(f(\omega_n^k)\) and \(f(\omega_n^{k+n/2})\) at once. All that remains is to compute the DFT of \(G\) and of \(H\) recursively.
The divide-and-conquer DFT can only handle polynomials of length \(2^m(m \in \mathbf{N}^ \ast )\): otherwise the two halves would differ in length at some level, and the right half would run out of coefficients. So before the first DFT, pad the sequence up to length \(2^m(m \in \mathbf{N}^\ast )\) (the high-order coefficients are filled with \(0\)), which makes it a polynomial whose highest term has degree \(2^m-1\).
We have to evaluate at \(n\) distinct values, so we evaluate at \(\omega_n^0,\omega_n^1,\omega_n^2,\cdots, \omega_n^{n-1} (n=2^m(m \in \mathbf{N}^ \ast ))\), which are \(2^m\) distinct values.
As for the code, the STL provides a complex number template, and you can also write your own. The difference is that with the STL's complex you can call exp to obtain \(\omega_n\). Computing \(\omega_n\) from the complex number given by Euler's formula is equivalent, though.
This completes the DFT part of the FFT algorithm: it converts a polynomial from its coefficient representation to its point-value representation.
Note that because we are working with complex roots of unity, the polynomial with \(n\) terms has to be padded with zeros in its high-order terms so that \(n = 2 ^ k, k \in \mathbf{N}^ \ast\).
Recursive FFT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | |
The time complexity is \(O(n\log n)\).
Implementation by doubling
The divide-and-conquer structure leaves room for further optimization. A radix-2 FFT separates the odd-degree and even-degree coefficients of the whole polynomial at every level, until only single coefficients are left. But this recursion costs extra memory. Instead, we can first mimic the recursion and split the coefficients inside the original array, and then merge the computed values by doubling.
The splitting is done with the bit-reversal permutation.
The merging, with the butterfly optimization, needs only \(O(1)\) extra space.
Bit-reversal permutation
Take a polynomial with \(8\) terms and trace the splitting by hand:
- Initial sequence: \(\{x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7\}\)
- After one split: \(\{x_0, x_2, x_4, x_6\},\{x_1, x_3, x_5, x_7 \}\)
- After two splits: \(\{x_0,x_4\} \{x_2, x_6\},\{x_1, x_5\},\{x_3, x_7 \}\)
- After three splits: \(\{x_0\}\{x_4\}\{x_2\}\{x_6\}\{x_1\}\{x_5\}\{x_3\}\{x_7 \}\)
The pattern: write the index of each element of the original sequence in binary and reverse the bits; the result is the index of the element's final position. For example, \(x_1\) has index 001, which reversed is 100, i.e. 4, and its final position is indeed 4. This transformation is called the bit-reversal permutation; the proof is left to the reader.
From this definition, we can compute where every index is sent in \(O(n)\) time:
Implementation of the bit-reversal permutation (\(O(n)\))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |
The bit-reversal permutation can also be computed in \(O(n)\) by a recurrence that goes through the indices in increasing order. Let \(len=2^k\), where \(k\) is the number of binary digits, and let \(R(x)\) be the number obtained by reversing the binary number \(x\) of length \(k\) (padded with leading \(0\)s). We want \(R(0),R(1),\cdots,R(n-1)\).
First, \(R(0)=0\).
We compute \(R(x)\) in increasing order of \(x\), so when we get to \(R(x)\), the value of \(R\left(\left\lfloor \dfrac{x}{2} \right\rfloor\right)\) is already known. Shift \(x\) right by one bit (divide it by \(2\)), reverse the result, and shift right by one bit again: this is the reversal of all bits of \(x\) except its lowest (binary) digit.
Now for the lowest bit. If it is \(0\), the highest bit after the reversal is \(0\). If it is \(1\), the highest bit after the reversal is \(1\), so we also have to add \(\dfrac{len}{2}=2^{k-1}\). Altogether,
For example, let \(k=5\) and \(len=(100000)_2\). To reverse \((11001)_2\):
- Consider \((1100)_2\). We know that \(R((1100)_2)=R((01100)_2)=(00110)_2\), and shifting it right by one bit gives \((00011)_2\).
- Consider the lowest bit. If it is \(1\), it is reversed into the highest bit of the number, that is, \((10000)_2=2^{k-1}\) is added to the reversed number; if it is \(0\), nothing changes.
Implementation of the bit-reversal permutation (\(O(n)\))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
Butterfly optimization
Given \(G(\omega_{n/2}^k)\) and \(H(\omega_{n/2}^k)\), we compute \(f(\omega_n^k)\) and \(f(\omega_n^{k+n/2})\) with these two formulas:
After the bit-reversal permutation, for given \(n, k\):
- \(G(\omega_{n/2}^k)\) is stored at array index \(k\), and \(H(\omega_{n/2}^k)\) at array index \(k + \dfrac{n}{2}\).
- \(f(\omega_n^k)\) will be stored at array index \(k\), and \(f(\omega_n^{k+n/2})\) at array index \(k + \dfrac{n}{2}\).
So we can overwrite the array at indices \(k\) and \(k + \frac{n}{2}\) directly, with no extra array to hold the values. This is called the butterfly operation, or more precisely the radix-2 butterfly operation.
In more detail, here is how the butterfly operation merges all segments of length \(\frac{n}{2}\):
- Let the segment length be \(s = \frac{n}{2}\).
- Iterate simultaneously over the left endpoints \(l_g = 0, 2s, 4s, \cdots, N-2s\) of the sequences \(\{G(\omega_{n/2}^k)\}\) and the left endpoints \(l_h = s, 3s, 5s, \cdots, N-s\) of the sequences \(\{H(\omega_{n/2}^k)\}\).
- To merge two segments, iterate over \(k = 0, 1, 2, \cdots, s-1\); here \(G(\omega_{n/2}^k)\) is stored at array index \(l_g + k\) and \(H(\omega_{n/2}^k)\) at array index \(l_h + k\).
- Compute \(f(\omega_n^k)\) and \(f(\omega_n^{k+n/2})\) with the butterfly operation and overwrite the values in place.
Inverse fast Fourier transform
The inverse Fourier transform can be expressed in terms of the Fourier transform. There are two ways to see this.
Linear algebra perspective
The IDFT (the inverse Fourier transform) converts the point-value form of the target polynomial into its coefficient form. The DFT itself is a linear transformation: treat the target polynomial as a vector and left-multiply it by a matrix to get the transformed vector, which mimics substituting the complex roots of unity into the polynomial:
We already have the result on the far left, and the \(x\) values in the middle correspond one-to-one to the points in the point-value representation of the target polynomial. So, by basic matrix algebra, we only have to left-multiply both sides by the inverse of the big matrix in the middle.
Because the entries of this matrix are so special, its inverse is special too: take the reciprocal of every entry, then divide by the transform length \(n\), and you have the inverse matrix.
Note: the length of the Fourier transform is not the length of the polynomials. It should be longer than the length of the product polynomial. The polynomials to be multiplied are not that long, so pad their high-order terms with \(0\).
To turn the computed values into the reciprocals of the original ones, note that by Euler's formula
So we can try taking the root of unity \(\omega_k\) to be \(\mathrm{e}^{-\frac{2\pi \mathrm{i}}{k}}\), which turns the computed values into the reciprocals of the original ones. The only extra step afterwards is to divide by the length \(n\); everything else is exactly the same as in the DFT. We can write one function with a parameter that is \(1\) or \(-1\) and multiply \(\pi\) by it. Passing \(1\) gives the DFT, and passing \(-1\) gives the IDFT.
Periodicity of the complex roots of unity
The relation between the IDFT and the DFT can also be understood through the periodicity of the complex roots of unity.
Let the original polynomial be \(f(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}=\sum_{i=0}^{n-1}a_ix^i\). The IDFT recovers the coefficient representation from the point-value representation.
We use a constructive approach. We know \(y_i=f\left( \omega_n^i \right),i\in\{0,1,\cdots,n-1\}\) and want \(\{a_0,a_1,\cdots,a_{n-1}\}\). Construct the polynomial
In other words, we treat \(\{y_0,y_1,y_2,\cdots,y_{n-1}\}\) as the coefficient representation of a polynomial \(A\).
From here there are two derivations, which correspond to two implementations.
Method 1
Let \(b_i=\omega_n^{-i}\). The point-value representation of the polynomial \(A\) at \(x=b_0,b_1,\cdots,b_{n-1}\) is \(\left\{ A(b_0),A(b_1),\cdots,A(b_{n-1}) \right\}\).
Rewriting the definition of \(A(x)\), we can express \(A(b_k)\) as
Let \(S\left(\omega_n^a\right)=\sum_{i=0}^{n-1}\left(\omega_n^a\right)^i\).
When \(a=0 \pmod{n}\), \(S\left(\omega_n^a\right)=n\).
When \(a\neq 0 \pmod{n}\), we shift the sum by one term and subtract:
That is,
Substituting back into the original expression,
So at the points \(b_i=\omega_n^{-i}\), the point-value representation of \(A\) is
To sum up: replace the root of unity by its reciprocal, run one FFT on \(\{y_0,y_1,y_2,\cdots,y_{n-1}\}\), and divide by \(n\). This gives the coefficient representation of \(f(x)\).
Method 2
Substitute \(\omega_n^i\) into \(A(x)\) directly.
The derivation is much the same as in Method 1, and we end up with \(A(\omega_n^k) = \sum_{j=0}^{n-1}a_jS\left(\omega_n^{j+k}\right)\).
\(S\left(\omega_n^{j+k}\right) = n\) if and only if \(j+k=0 \pmod{n}\); otherwise it is \(0\). Hence \(A(\omega_n^k) = a_{(n-k)\bmod n}\cdot n\).
So we can also recover the coefficient representation of \(f(x)\) by applying the DFT to \(\{y_0,y_1,y_2,\cdots,y_{n-1}\}\), dividing by \(n\), and then reversing the last \(n - 1\) elements.
Implementation
So a single FFT function can do both the DFT and the IDFT. Here is the code:
Non-recursive FFT (Method 1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | |
Non-recursive FFT (Method 2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | |
FFT template (HDU 1402 - A * B Problem Plus)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | |
References
- Taojiang's Algorithm Notes (in Chinese).
This page is an unofficial English translation of the original OI Wiki page (revision 9e24fbc6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: H-J-Granger, ranwen, abc1763613206, Ahacad, Allenyou1126, AndrewWayne, AngelKitty, AtomAlpaca, Backl1ght, billchenchina, c-forrest, CCXXXI, Cheuring, Chrogeek, ChungZH, countercurrent-time, DepletedPrism, Early0v0, EarthMessenger, Enter-tainer, F1shAndCat, GavinZhengOI, Gesrua, Great-designer, greyqz, henryrabbit, heroming, hly1204, Ir1d, isdanni, jiang1997, kenlig, lucifer1004, Menci, muoshuosha, NachtgeistW, needtocalmdown, opsiff, ouuan, partychicken, schtonn, Sshwy, StudyingFather, SukkaW, Taoran-01, Tiphereth-A, TrisolarisHD, untitledunrevised, Xeonacid, YouXam, Yukimaikoriya, 24OI-bot, ksyx, shuzhouliu, limpidautumn, ZnPdCo, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.