# Polynomial Multiplication Using the FFT

DevFeed: [Polynomial Multiplication Using the FFT](<https://devfeed.tech/articles/polynomial-multiplication-using-the-fft-40459.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2022/11/16/polynomial-multiplication-using-the-fft/>)

Published: 2022-11-16T08:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [polynomials](<https://devfeed.tech/topics/polynomials.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [NumPy](<https://devfeed.tech/topics/numpy.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arrays](<https://devfeed.tech/tags/arrays.md>), [efficiently](<https://devfeed.tech/tags/efficiently.md>), [fft](<https://devfeed.tech/tags/fft.md>), [fourier-transform](<https://devfeed.tech/tags/fourier-transform.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [polynomial-interpolation](<https://devfeed.tech/tags/polynomial-interpolation.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

## AI overview

This tutorial explains how to multiply two polynomials efficiently using the Fast Fourier Transform. It contrasts the naive O(n^2) approach with polynomial interpolation, pointwise multiplication, and carefully chosen roots of unity that enable reusable computations.

## Source excerpt

Problem: Compute the product of two polynomials efficiently. Solution: import numpy from numpy.fft import fft, ifft def poly_mul(p1, p2): """Multiply two polynomials. p1 and p2 are arrays of coefficients in degree-increasing order. """ deg1 = p1.shape[0] - 1 deg2 = p1.shape[0] - 1 # Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1 total_num_pts = 2 * (deg1 + deg2) next_power_of_2 = 1 << (total_num_pts - 1).