# The fast Fourier transform Flashcards

what is the degree of the product of two degree-d polynomials?

a polynomial of degree *2d*

Naively how much time does it take to multiply two polynomials for degree d?

O(d^2), since for every coefficient of the product polynomial, it takes O(k) steps, and there are 2d+1 coefficients resulting with:

O(1) + O(2) + .. + O(2d) = O(d^2)

How the fact the “A degree-d polynomial is **uniquely** charactersized by its values at any d+1 distinct points” gives us an *alternative representation* of polynomials?

for a degree-n polynomial A, how much time does it take to compute A(z) for some z?

How much time does it take to compute C(z), using A(z)*B(z)

Both take O(n).

*Describe the process of identifying the coefficents of C(x) = A(x)*B(x)*

input: A and B coefficient.

Evaluation of A(z) * B(z) = C(z) for 2d+1 points.

Interpolation back to find the coefficient of C(x)

*What is the great buzz behind FFT?*

it can evaluate a polynomial of degree d<=n, for n points in O(nlogn) time instead of O(n^2)

What is the first interesting idea as to how to reduce the time complexity for evaluation?

we can choose positive-negative paris, thus having the computations required for A(x) and A(-x) overlap a lot since for even power k, pow(x,k) = pow(-x, k).

Explain why A(x) can be written as:

A’(x^2) + xA’‘(x^2)

where A’ = even coefficients and A’’ = odd coefficients.

Analyze the improvement in run-time

A is of degree-n -> Aeven and Aodd are of degree d/2.

we need to evalutate only n/2 points. x0^2, x1^2…

That is,

first problem: evalute n points on degree n polynomial.

updated problem: evaluate n/2 points on two d/2 degree polynomial. Then finding A(x) demands O(n) arithmetic.

T(n) = 2T(n/2) + O(n) = O(nlogn)

*What is the problem with this method of pos/min points?*

How can we have complex number which satisfies the recursion requirements. That is, that the next call of the n/2 points are still plus/neg couples?

We reverse-engineer the problem:

we start with 1 and each time find the roots.

since each number has 2 roots in the complex realm, we have:

1 -> -1, 1 -> -i, i, -1, 1 -> …. till we reach n points.

which are **the complex nth roots of unity. The solutions for the equation z^n = 1**

What is the fast formula for extracting all nth roots of unity?

If n is even, what is special about the nth roots?

They are plus-minus paired!

and when squared, we get the (n/2)nd roots of unity.

Write the fast Fourier transform

Write in matrix form the transformation for coefficient of a polynomial to values, given n values.