Fast Fourier Transform

This article will introduce an algorithm that supports the calculation of the multiplication of two polynomials of degree n in O(nlog n) time, which is more efficient than the naive O(n^2) algorithm. Since the multiplication of two integers can also be treated as polynomial multiplication, this algorithm can also be used to speed up the multiplication of large integers.

We now introduce two polynomials A and B:

A = 5x^2 + 3x + 7

B = 7x^2 + 2x + 1

The product of two polynomials, C = A * B, can be solved in O(n^2) time complexity (where n is the degree of the A or B polynomial) by using high school method.

For this simple algorithm, the time complexity of calculating each item is O(n), and there are O(n) items in total, so the time complexity is O(n^2).

Can it be accelerated to reduce its time complexity? If we use Fast Fourier Transform, we can reduce its complexity to O(nlog n).

Fourier Transform is a method of analyzing signals. It can analyze the components of a signal and can also use these components to synthesize signals. Many waveforms can be used as components of a signal, and the Fourier transform uses sine waves as components of the signal.

Assuming that f(t) is a function of time t, the Fourier transform can detect the extent to which a period of frequency ω occurs at f(t):

Its inverse transformation is

The form of the inverse transformation is very similar to the forward transformation, the denominator 2π happens to be the period of the exponential function.

The Fourier transform is equivalent to performing a continuous inner product of a function in the time domain and a complex exponential function with a period of 2π. The inverse transformation is still an inner product.

Fourier transform has a corresponding convolution theorem, which can convert the convolution in the time domain into a product in the frequency domain, and can also convert the convolution in the frequency domain into a product in the time domain.

Discrete Fourier transform (DFT) is a discrete form of Fourier transform in both the time domain and frequency domain. It converts the time domain sampling of the signal into the frequency domain of its DTFT (discrete-time Fourier transform) sampling.

The Fourier transform is the inner product of continuous functions in integral form, and the discrete Fourier transform is the inner product of summation form. For sequeunce X_n, where n is integer such that 0 <= n < N, its DFT is

FFT is an algorithm that efficiently implements DFT, called Fast Fourier Transform (FFT). It does not make new discoveries about the theory of Fourier transform, but it can be said to be a big step forward for the application of discrete Fourier transform in computer systems or digital systems. The fast number theory transform (NTT) is an implementation of the fast Fourier transform (FFT) based on number theory.

In 1965, Cooley and Tukey published the Fast Fourier Transform algorithm. In fact, FFT had been discovered long before this, but modern computers had not been invented at that time, and people did not realize the importance of FFT. Some investigators believe that FFT was discovered by Runge and König in 1924. But in fact Gauss invented this algorithm as early as 1805, but it has never been published.