Skip to content

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\):

\[ \begin{aligned} A ={}& 5x^2 + 3x + 7 \\ B ={}& 7x^2 + 2x + 1 \\ \end{aligned} \]

Their product \(C = A \times B\) can be computed in \(O(n^2)\) time (here \(n\) is the degree of \(A\) or \(B\)):

\[ \begin{aligned} C ={}& A \times B \\ ={}& 35x^4 + 31x^3 + 60x^2 + 17x + 7 \end{aligned} \]

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)\):

\[ F(\omega)=\mathbb{F}[f(t)]=\int_{-\infty}^{\infty}f(t)\mathrm{e}^{-\mathrm{i}{\omega}t}dt \]

Its inverse transform is

\[ f(t)=\mathbb{F}^{-1}[F(\omega)]=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)\mathrm{e}^{\mathrm{i}{\omega}t}d\omega \]

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:

\[ X_k=\sum_{n=0}^{N-1}x_n\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}kn} \]

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,

\[ \hat{x}=\mathcal{F}x \]

As with the integral form, its inverse discrete Fourier transform (IDFT) is:

\[ x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k\mathrm{e}^{\mathrm{i}\frac{2\pi}{N}kn} \]

which can be written as:

\[ x=\mathcal{F}^{-1}\hat{x} \]

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:

\[ \dbinom{n}{3}+\dbinom{n}{7}+\dbinom{n}{11}+\dbinom{n}{15}+\ldots \]

Define the function \(f(x)\) as:

\[ f(x)={(1+x)}^n=\dbinom{n}{0}x^0+\dbinom{n}{1}x^1+\dbinom{n}{2}x^2+\dbinom{n}{3}x^3+\ldots \]

Evaluating it at a fourth root of unity gives \(f(\mathrm{i})\), which expands to:

\[ f(\mathrm{i})={(1+\mathrm{i})}^n=\dbinom{n}{0}+\dbinom{n}{1}\mathrm{i}-\dbinom{n}{2}-\dbinom{n}{3}\mathrm{i}+\ldots \]

The following sum then cancels all the other terms:

\[ f(1)+\mathrm{i}f(\mathrm{i})-f(-1)-\mathrm{i}f(-\mathrm{i})=4\dbinom{n}{3}+4\dbinom{n}{7}+4\dbinom{n}{11}+4\dbinom{n}{15}+\ldots \]

So the answer to this problem is:

\[ \dbinom{n}{3}+\dbinom{n}{7}+\dbinom{n}{11}+\dbinom{n}{15}+\ldots=\frac{2^n+\mathrm{i}(1+\mathrm{i})^n-\mathrm{i}(1-\mathrm{i})^n}{4} \]

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:

\[ \begin{bmatrix} X_{0} \\ X_{1} \\ X_{2} \\ \vdots \\ X_{N-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \alpha & \alpha^{2} & \cdots & \alpha^{N-1} \\ 1 & \alpha^{2} & \alpha^{4} & \cdots & \alpha^{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha^{N-1} & \alpha^{2(N-1)} & \cdots & \alpha^{(N-1)(N-1)} \end{bmatrix} \begin{bmatrix} x_{0} \\ x_{1} \\ x_{2} \\ \vdots \\ x_{N-1} \end{bmatrix} \]

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:

\[ f(x) = a_0 + a_1x + a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6+a_7x^7 \]

Split the terms into two groups by the parity of their degree, and factor an \(x\) out of the right-hand group:

\[ \begin{aligned} f(x) &= (a_0+a_2x^2+a_4x^4+a_6x^6) + (a_1x+a_3x^3+a_5x^5+a_7x^7)\\ &= (a_0+a_2x^2+a_4x^4+a_6x^6) + x(a_1+a_3x^2+a_5x^4+a_7x^6) \end{aligned} \]

Build two new functions, one from the even-degree coefficients and one from the odd-degree coefficients:

\[ \begin{aligned} G(x) &= a_0+a_2x+a_4x^2+a_6x^3\\ H(x) &= a_1+a_3x+a_5x^2+a_7x^3 \end{aligned} \]

The original \(f(x)\) can then be written in terms of them:

\[ f(x)=G\left(x^2\right) + x \times H\left(x^2\right) \]

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:

\[ \begin{aligned} f(\omega_n^k) &= G((\omega_n^k)^2) + \omega_n^k \times H((\omega_n^k)^2) \\ &= G(\omega_n^{2k}) + \omega_n^k \times H(\omega_n^{2k}) \\ &= G(\omega_{n/2}^k) + \omega_n^k \times H(\omega_{n/2}^k) \end{aligned} \]

and:

\[ \begin{aligned} f(\omega_n^{k+n/2}) &= G(\omega_n^{2k+n}) + \omega_n^{k+n/2} \times H(\omega_n^{2k+n}) \\ &= G(\omega_n^{2k}) - \omega_n^k \times H(\omega_n^{2k}) \\ &= G(\omega_{n/2}^k) - \omega_n^k \times H(\omega_{n/2}^k) \end{aligned} \]

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
#include <cmath>
#include <complex>

using Comp = std::complex<double>;  // STL complex

constexpr Comp I(0, 1);  // i
constexpr int MAX_N = 1 << 20;

Comp tmp[MAX_N];

// rev=1, DFT; rev=-1, IDFT
// After calling this function, remember to handle the normalization factor
void DFT(Comp* f, int n, int rev) {
  if (n == 1) return;
  for (int i = 0; i < n; ++i) tmp[i] = f[i];
  // Even indices go to the left half, odd indices to the right half
  for (int i = 0; i < n; ++i) {
    if (i & 1)
      f[n / 2 + i / 2] = tmp[i];
    else
      f[i / 2] = tmp[i];
  }
  Comp *g = f, *h = f + n / 2;
  // Recursive DFT
  DFT(g, n / 2, rev), DFT(h, n / 2, rev);
  // cur is the current root of unity; for k = 0 it is omega^0_n = 1.
  // step takes one root of unity to the next: omega^k_n = step*omega^{k-1}_n.
  // Its definition is equivalent to exp(I*(-2*M_PI/n*rev))
  Comp cur(1, 0), step(cos(2 * M_PI / n), sin(-2 * M_PI * rev / n));
  for (int k = 0; k < n / 2;
       ++k) {  // F(omega^k_n) = G(omega^k_{n/2}) + omega^k_n*H(omega^k_{n/2})
    tmp[k] = g[k] + cur * h[k];
    // F(omega^{k+n/2}_n) = G(omega^k_{n/2}) - omega^k_n*H(omega^k_{n/2})
    tmp[k + n / 2] = g[k] - cur * h[k];
    cur *= step;
  }
  for (int i = 0; i < n; ++i) f[i] = tmp[i];
}

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 applied before the FFT and the IFFT
 * Swaps position i with the position whose index is i with its bits reversed
 * len must be a power of 2
 */
void change(Complex y[], int len) {
  // Initially i is 0...01 and j is 10...0: mirror images of each other in binary.
  // Then i is incremented step by step while j stays its mirror image, until i = 1...11.
  for (int i = 1, j = len / 2, k; i < len - 1; i++) {
    // Swap elements whose indices are bit reversals of each other; i < j ensures one swap per pair
    if (i < j) swap(y[i], y[j]);
    // i gets an ordinary + 1 and j a bit-reversed + 1, so i and j always stay reversals.
    // Here k stands for the highest bit that is 0. j first has the run of 1s in its
    // high bits subtracted until a 0 is met, and then that bit is added.
    // Count how often the bits of j are flipped: the highest bit is flipped n times,
    // the second highest n/2 times, and so on, so the time complexity is:
    // T(n) = n + n/2 + n/4 + ... = O(n)
    k = len / 2;
    while (j >= k) {
      j = j - k;
      k = k / 2;
    }
    j += k;
  }
}

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,

\[ R(x)=\left\lfloor \frac{R\left(\left\lfloor \frac{x}{2} \right\rfloor\right)}{2} \right\rfloor + (x\bmod 2)\times \frac{len}{2} \]

For example, let \(k=5\) and \(len=(100000)_2\). To reverse \((11001)_2\):

  1. Consider \((1100)_2\). We know that \(R((1100)_2)=R((01100)_2)=(00110)_2\), and shifting it right by one bit gives \((00011)_2\).
  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
// Again, len must be a power of 2
// rev[i] is the value of i with its bits reversed
void change(Complex y[], int len) {
  for (int i = 0; i < len; ++i) {
    rev[i] = rev[i >> 1] >> 1;
    if (i & 1) {  // If the last bit is 1, it is reversed into len/2
      rev[i] |= len >> 1;
    }
  }
  for (int i = 0; i < len; ++i) {
    if (i < rev[i]) {  // Ensures each pair is swapped only once
      swap(y[i], y[rev[i]]);
    }
  }
  return;
}

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:

\[ \begin{aligned} f(\omega_n^k) & = G(\omega_{n/2}^k) + \omega_n^k \times H(\omega_{n/2}^k) \\ f(\omega_n^{k+n/2}) & = G(\omega_{n/2}^k) - \omega_n^k \times H(\omega_{n/2}^k) \end{aligned} \]

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}\):

  1. Let the segment length be \(s = \frac{n}{2}\).
  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)\}\).
  3. 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\).
  4. 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:

\[ \begin{bmatrix}y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{n-1} \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_n^1 & \omega_n^2 & \omega_n^3 & \cdots & \omega_n^{n-1} \\ 1 & \omega_n^2 & \omega_n^4 & \omega_n^6 & \cdots & \omega_n^{2(n-1)} \\ 1 & \omega_n^3 & \omega_n^6 & \omega_n^9 & \cdots & \omega_n^{3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_n^{n-1} & \omega_n^{2(n-1)} & \omega_n^{3(n-1)} & \cdots & \omega_n^{(n-1)^2} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-1} \end{bmatrix} \]

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

\[ \frac{1}{\omega_k}=\omega_k^{-1}=\mathrm{e}^{-\frac{2\pi \mathrm{i}}{k}}=\cos\left(\frac{2\pi}{k}\right)+\mathrm{i} \sin\left(-\frac{2\pi}{k}\right) \]

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

\[ A(x)=\sum_{i=0}^{n-1}y_ix^i \]

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

\[ \begin{aligned} A(b_k)&=\sum_{i=0}^{n-1}f(\omega_n^i)\omega_n^{-ik}=\sum_{i=0}^{n-1}\omega_n^{-ik}\sum_{j=0}^{n-1}a_j(\omega_n^i)^{j}\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j\omega_n^{i(j-k)}=\sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}\left(\omega_n^{j-k}\right)^i\\ \end{aligned} \]

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:

\[ \begin{aligned} S\left(\omega_n^a\right)&=\sum_{i=0}^{n-1}\left(\omega_n^a\right)^i\\ \omega_n^a S\left(\omega_n^a\right)&=\sum_{i=1}^{n}\left(\omega_n^a\right)^i\\ S\left(\omega_n^a\right)&=\frac{\left(\omega_n^a\right)^n-\left(\omega_n^a\right)^0}{\omega_n^a-1}=0\\ \end{aligned} \]

That is,

\[ S\left(\omega_n^a\right)= \begin{cases} n,&a=0\\ 0,&a\neq 0 \end{cases} \]

Substituting back into the original expression,

\[ A(b_k)=\sum_{j=0}^{n-1}a_jS\left(\omega_n^{j-k}\right)=a_k\cdot n \]

So at the points \(b_i=\omega_n^{-i}\), the point-value representation of \(A\) is

\[ \begin{aligned} &\left\{ (b_0,A(b_0)),(b_1,A(b_1)),\cdots,(b_{n-1},A(b_{n-1})) \right\}\\ =&\left\{ (b_0,a_0\cdot n),(b_1,a_1\cdot n),\cdots,(b_{n-1},a_{n-1}\cdot n) \right\} \end{aligned} \]

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
/*
 * Performs the FFT
 * len must be of the form 2^k
 * on == 1 gives the DFT, on == -1 gives the IDFT
 */
void fft(Complex y[], int len, int on) {
  // Bit-reversal permutation
  change(y, len);
  // Simulate the merging: first from length 1 to length 2, and so on up to length len.
  for (int h = 2; h <= len; h <<= 1) {
    // wn: the step between consecutive roots of unity at this level: w^1_h
    Complex wn(cos(2 * PI / h), sin(on * 2 * PI / h));
    // Merge, len / h times in total.
    for (int j = 0; j < len; j += h) {
      // The current root of unity: it starts at 1 = w^0_n, then advances by a factor of wn: w^1_n
      // ...
      Complex w(1, 0);
      for (int k = j; k < j + h / 2; k++) {
        // The left part and the right part hold the solutions of the subproblems
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        // This adds up the divide-and-conquer results of the two parts
        y[k] = u + t;
        y[k + h / 2] = u - t;
        // The ω in the second half of a "step" is always the negative of the one in the first half:
        // a point on the "red circle" comes back after a full turn, and after half a turn it is its negative.
        // The square of the negative of a number equals the square of the number itself.
        w = w * wn;
      }
    }
  }
  // For the IDFT, an entry of the inverse matrix is not just the reciprocal of the original entry: it is also divided by len.
  if (on == -1) {
    for (int i = 0; i < len; i++) {
      y[i].x /= len;
      y[i].y /= len;
    }
  }
}
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
/*
 * Performs the FFT
 * len must be of the form 2^k
 * on == 1 gives the DFT, on == -1 gives the IDFT
 */
void fft(Complex y[], int len, int on) {
  change(y, len);
  for (int h = 2; h <= len; h <<= 1) {             // Simulate the merging
    Complex wn(cos(2 * PI / h), sin(2 * PI / h));  // Compute the current root of unity
    for (int j = 0; j < len; j += h) {
      Complex w(1, 0);  // Compute the current root of unity
      for (int k = j; k < j + h / 2; k++) {
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        y[k] = u + t;  // This adds up the divide-and-conquer results of the two parts
        y[k + h / 2] = u - t;
        // The ω in the second half of a "step" is always the negative of the one in the first half:
        // a point on the "red circle" comes back after a full turn, and after half a turn it is its negative.
        // The square of the negative of a number equals the square of the number itself.
        w = w * wn;
      }
    }
  }
  if (on == -1) {
    reverse(y + 1, y + len);
    for (int i = 0; i < len; i++) {
      y[i].x /= len;
      y[i].y /= len;
    }
  }
}
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
#include <cmath>
#include <cstring>
#include <iostream>

const double PI = acos(-1.0);

struct Complex {
  double x, y;

  Complex(double _x = 0.0, double _y = 0.0) {
    x = _x;
    y = _y;
  }

  Complex operator-(const Complex &b) const {
    return Complex(x - b.x, y - b.y);
  }

  Complex operator+(const Complex &b) const {
    return Complex(x + b.x, y + b.y);
  }

  Complex operator*(const Complex &b) const {
    return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
  }
};

/*
 * The bit-reversal permutation applied before the FFT and the IFFT
 * Swaps position i with the position whose index is i with its bits reversed
 *len must be a power of 2
 */
void change(Complex y[], int len) {
  int i, j, k;

  for (int i = 1, j = len / 2; i < len - 1; i++) {
    if (i < j) std::swap(y[i], y[j]);

    // Swap elements whose indices are bit reversals of each other; i<j ensures one swap per pair
    // i gets an ordinary + 1 and j a bit-reversed + 1, so i and j always stay reversals
    k = len / 2;

    while (j >= k) {
      j = j - k;
      k = k / 2;
    }

    if (j < k) j += k;
  }
}

/*
 * Performs the FFT
 *len must be of the form 2^k
 *on == 1 gives the DFT, on == -1 gives the IDFT
 */
void fft(Complex y[], int len, int on) {
  change(y, len);

  for (int h = 2; h <= len; h <<= 1) {
    Complex wn(cos(2 * PI / h), sin(on * 2 * PI / h));

    for (int j = 0; j < len; j += h) {
      Complex w(1, 0);

      for (int k = j; k < j + h / 2; k++) {
        Complex u = y[k];
        Complex t = w * y[k + h / 2];
        y[k] = u + t;
        y[k + h / 2] = u - t;
        w = w * wn;
      }
    }
  }

  if (on == -1) {
    for (int i = 0; i < len; i++) {
      y[i].x /= len;
    }
  }
}

constexpr int MAXN = 200020;
Complex x1[MAXN], x2[MAXN];
char str1[MAXN / 2], str2[MAXN / 2];
int sum[MAXN];
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> str1 >> str2) {
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int len = 1;

    while (len < len1 * 2 || len < len2 * 2) len <<= 1;

    for (int i = 0; i < len1; i++) x1[i] = Complex(str1[len1 - 1 - i] - '0', 0);

    for (int i = len1; i < len; i++) x1[i] = Complex(0, 0);

    for (int i = 0; i < len2; i++) x2[i] = Complex(str2[len2 - 1 - i] - '0', 0);

    for (int i = len2; i < len; i++) x2[i] = Complex(0, 0);

    fft(x1, len, 1);
    fft(x2, len, 1);

    for (int i = 0; i < len; i++) x1[i] = x1[i] * x2[i];

    fft(x1, len, -1);

    for (int i = 0; i < len; i++) sum[i] = int(x1[i].x + 0.5);

    for (int i = 0; i < len; i++) {
      sum[i + 1] += sum[i] / 10;
      sum[i] %= 10;
    }

    len = len1 + len2 - 1;

    while (sum[len] == 0 && len > 0) len--;

    for (int i = len; i >= 0; i--) cout << char(sum[i] + '0');

    cout << '\n';
  }

  return 0;
}

References

  1. Taojiang's Algorithm Notes (in Chinese).