Skip to content
Tutorials Center
My learning

Topics

Lesson 192 of 225 ยท Math and Bit Manipulation

FFT and Polynomial Multiplication

Multiply polynomials and big numbers in O(n log n) with the Fast Fourier Transform and the exact Number Theoretic Transform. Clear Python code and diagrams.

Multiplying two polynomials sounds like a school exercise, but the same operation hides inside many algorithm problems: multiplying huge integers, counting how many pairs of numbers add up to each possible sum, matching strings with wildcards, even combining probability distributions. The direct method needs nยฒ multiplications. The Fast Fourier Transform (FFT) does it in O(n log n), which is the difference between waiting a minute and waiting a blink for n = 10โถ.

The operation is called convolution. This lesson starts with the slow version, explains the beautiful trick that makes the fast one possible, and builds both a floating-point FFT and an exact Number Theoretic Transform (NTT) in Python.

Polynomial multiplication, the slow way

Write a polynomial as a list of coefficients, lowest power first: [1, 2, 3] means 1 + 2x + 3xยฒ. To multiply, every term of A multiplies every term of B, and the product of x^i and x^j is x^(i+j):

C[i + j] += A[i] * B[j]

That double loop is O(nยทm). It is also exactly the "convolution" of the two lists.

Python Naive convolution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second example shows why this matters beyond algebra: multiplying the "polynomial" of one die by itself counts the ways to get each total with two dice.

The big idea: change the representation

A degree-n-1 polynomial can be stored in two equivalent ways:

  • Coefficient form: the n coefficients.
  • Point-value form: its values at n distinct points.

In point-value form, multiplication is trivial: to get the product's value at x, just multiply the two values at x. That is O(n) work. The catch is converting between forms. Evaluating at n arbitrary points costs O(nยฒ), which brings us back to square one.

The FFT's insight is to choose the points cleverly: the n-th roots of unity, the complex numbers w^k where w = e^(2ฯ€i/n). Because they are so symmetric, the evaluation can be split in half again and again, giving O(n log n).

flowchart LR
    A["Coefficients of A and B"] -->|"FFT, O(n log n)"| V["Values at n roots of unity"]
    V -->|"multiply pointwise, O(n)"| P["Values of A*B"]
    P -->|"inverse FFT, O(n log n)"| C["Coefficients of A*B"]
    A -.->|"naive, O(n^2)"| C

The detour through point-value form beats the direct route for large n.

How the FFT splits the work

Split a polynomial into its even and odd coefficients:

A(x) = E(xยฒ) + x ยท O(xยฒ)

where E has the even-index coefficients and O the odd-index ones. Each has half the size. For the n-th root of unity w^k:

  • A(w^k) = E(w^(2k)) + w^k ยท O(w^(2k))
  • A(w^(k + n/2)) = E(w^(2k)) โˆ’ w^k ยท O(w^(2k)), because w^(n/2) = โˆ’1.

The squares w^(2k) are exactly the (n/2)-th roots of unity, so E and O need only half as many evaluations, which we get by recursion. One subproblem pair yields two outputs per k with a single multiplication. The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n), the same shape as merge sort and a classic divide and conquer design.

The inverse transform is the same algorithm with w replaced by its conjugate, followed by dividing every result by n.

Python A recursive FFT and polynomial multiplication

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two details to notice. First, the length must be a power of two at least len(a) + len(b) - 1, so we pad with zeros; otherwise the product would "wrap around". Second, the results are floating-point, so we round them back to integers.

Counting the work

Naive multiplication of two polynomials with 1024 coefficients each performs 1,048,576 multiplications. The FFT approach pads to 2048 and does three transforms, each with (2048 / 2) * 11 = 11,264 butterfly steps, about 33,800 in total.

Python Naive versus FFT operation counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a million coefficients the FFT needs thousands of times fewer steps. For tiny inputs the naive loop wins, because the FFT has a larger constant factor.

Multiplying huge integers

A number is a polynomial in disguise: 1234 is 4 + 3x + 2xยฒ + 1xยณ evaluated at x = 10. To multiply two big integers, turn their digits into coefficient lists, convolve, and then carry (a coefficient may exceed 9).

Python Big-integer multiplication with a convolution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here we used the slow convolve to show the idea; swap in multiply_fft for inputs with hundreds of thousands of digits. Real libraries group several digits into one coefficient to keep the lists short.

Exact results with the Number Theoretic Transform

Complex floating-point numbers lose precision when coefficients or lengths get large (roughly when sums exceed 10ยนโด or so). The NTT is the same algorithm done in integers modulo a special prime, so every result is exact.

We need a prime p for which p โˆ’ 1 has a large power-of-two factor, so that an n-th root of unity exists modulo p for each power of two n. The popular choice is p = 998244353 = 119 ยท 2ยฒยณ + 1, with primitive root 3. The root of unity of order n is pow(3, (p - 1) // n, p), and the inverse transform uses its modular inverse, then divides by n.

Python Exact convolution with the NTT

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Use the NTT when the problem asks for an answer "modulo 998244353" (very common in contests), or when exactness matters more than speed. If you need the true integer product and its coefficients are huge, run the NTT with two or three different primes and combine them with the Chinese Remainder Theorem.

When is convolution the right tool?

Problem Why it is a convolution
Count pairs (i, j) with a[i] + b[j] = s for every s Product of indicator polynomials
Multiply huge integers Digits are coefficients
String matching with wildcards Sum of products of character codes
Distribution of a sum of independent variables Product of probability polynomials
Counting subsets by total weight Product of (1 + x^w) factors

Common mistakes

  • Not padding far enough. The transform length must be at least len(a) + len(b) - 1, rounded up to a power of two.
  • Forgetting the division by n after the inverse transform.
  • Trusting floats blindly. Always round, and if values may be large use the NTT or split coefficients into smaller chunks.
  • Using the NTT with the wrong modulus. Only primes of the form c ยท 2^k + 1 support long power-of-two transforms.
  • Reaching for FFT on small inputs. Below roughly a few dozen coefficients the double loop is faster and simpler.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the time complexity of multiplying two degree-n polynomials with the FFT?

    Two forward transforms, a pointwise product and one inverse transform each cost O(n log n) or less.
  2. 2. Why does multiplication become easy in point-value form?

    (A*B)(x) = A(x) * B(x), so multiplying n pairs of values takes O(n) time.
  3. 3. Which identity lets the FFT reuse subproblem results for two outputs?

    Because w^(n/2) is -1, the same even and odd evaluations give both A(w^k) and A(w^(k+n/2)).
  4. 4. When is the NTT preferable to the floating-point FFT?

    The NTT works with integers modulo a prime, so there is no rounding error.
  5. 5. You multiply polynomials with 100 and 60 coefficients. What is the smallest power-of-two transform length?

    The product has 100 + 60 - 1 = 159 coefficients, and the next power of two at or above 159 is 256.

Summary

  • Polynomial multiplication is convolution: C[i + j] += A[i] * B[j], O(nยฒ) done directly.
  • Evaluating at the n-th roots of unity lets the FFT split into even and odd halves, so the transform costs O(n log n).
  • Multiply pointwise in the transformed domain, then apply the inverse FFT and divide by n.
  • Pad to a power of two of at least len(a) + len(b) - 1; round floating-point results.
  • The NTT does the same thing modulo a prime like 998244353 for exact answers.
  • Convolution solves sum-counting, big-integer multiplication and many matching problems.

Next: Skip Lists