# Notes for FFT Course

:::success
source: [MIT OCW 6.046 2015 spring](https://youtu.be/iTMn0Kt18tg)
:::

## Polynomials

$$
\begin{align}
A(x) &= a_0x^0 + a_1x^1 + \cdots + a_{n-1}x^{n-1} \\
&= \sum_{k=0}^{n-1}a_kx^k \\
&= <a_0, a_1, \cdots, a_n-1>
\end{align}
$$

### Operations of Polynomials

1. Evaluate: $A(x),x_0 \rightarrow A(x_0)$
- Naive: $O(n^2)$
- Horner's Rule: $A(x) = a_0 + x(a_1 + x(\cdots)) \Rightarrow O(n)$ with constant time mult and add two real numbers.
2. Addition: $A(x),B(x) \rightarrow C(x) = A(x) + B(x)\ \forall x$
- $c_k = a_k + b_k \ \forall k \Rightarrow O(n)$
3. Multiplication: $A(x),B(x) \rightarrow C(x) = A(x) \cdot B(x)\ \forall x$
- Naive:
$\begin{align}
&A(x) \cdot B(x) \\
&=(a_0x^0 + a_1x^1 + \cdots + a_{n-1}x^{n-1})(b_0x^0 + b_1x^1 + \cdots + b_{n-1}x^{n-1}) \\
&= a_0b_0 + (a_0b_1 + a_1b_0)x + \cdots \\
&= \sum_{k=0}^{n-1}{\sum_{i+j=k}{a_ib_jx^k}}
\end{align} \\
\rightarrow c_k = \sum_{i+j=k}{a_ib_j}
\rightarrow O(n^2)$
- Goal: $O(n^2) \rightarrow O(n \log_2 n)$

### Convolution

Dot product of all possible shifts of two vectors.

### Representation of Polynomials
1. Coefficient Vector: $a_0 + a_1x + a_2x^2 + \cdots$
2. Roots: $r_0, r_1, \cdots, r_{n-1} \rightarrow A(x) = a(x - r_0)(x - r_1) \cdots$
3. Samples: $(x_k, y_k), A(x_k) = y_k, \forall k \in \{0, 1, \cdots n-1\}$, $x_k$'s distinct.

Roots are bad for adding and converting (only good for multiplying).

### Operations and Their Time Complexity for Different Representations

| Operation | Coeff. | Roots | Samples |
| -------- | -------- | -------- | -------- |
| Evaluate | $O(n)$ | $O(n)$ | $O(n^2)$ (bad) |
| Addition | $O(n)$ | $\infty$ (bad) | $O(n)$ |
| Multiplication | $O(n^2)$ (bad) | $O(n)$ | $O(n)$ |

For evaluating samples representation, using something like Lagrange polyomial takes $O(n^2)$ time.
> "No representation is perfect. Life sucks."

Roots are bad (impossible to convert in arithmetic model), so we only look at column 1 and 3 and try to convert between them in $O(n \log n)$ time.

## Converting Coeff. $\leftrightarrow$ Samples

### Naive

Takes $O(n^2)$ time. $O(n)$ for each sample, $O(n)$ samples.

### Matrix View

$$
\begin{bmatrix}
1 & x_0 & x_0^2 & \cdots & x_0^{n-1}\\
1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\
1 & x_2 & x_2^2 & \cdots & x_2^{n-1}\\
\vdots & \vdots & \vdots & \vdots & \vdots & \\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1}
\end{bmatrix}
\begin{bmatrix}
a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1}
\end{bmatrix} =
\begin{bmatrix}
y_0 \\ y_1 \\ y_2 \\ \vdots \\ y_{n-1}
\end{bmatrix}
$$
$V_{jk} = x_j^k$
- Coeff. $\rightarrow$ Samples $\equiv V \cdot A$
- Samples $\rightarrow$ Coeff. $\equiv V \backslash A$
- Gaussian Elimination $\rightarrow O(n^3)$
- $V^{-1} \cdot A \rightarrow O(n^2)$

> Can we make that better?

## Divide & Conquer

Let's try divide and conquer for this problem.
Our goal: $A(x)\ \forall x \in X$
Then we can think of divide $A(x)$ into $A_{even}(x)$ and $A_{odd}(x)$, so the procedure will be:
1. **Divide**
Divide $A(x)$ into $A_{even}(x)$ and $A_{odd}(x)$ s.t. $A_{even}(x) = \sum_{k=0}^{n/2 - 1}a_{2k}x^k,\ A_{odd}(x) = \sum_{k=0}^{n/2 - 1}a_{2k + 1}x^k$
Complexity: $O(n)$

2. **Conquer**
Recursively solve $A_{even}(x)$ and $A_{odd}(x)$

3. **Combine**
$A(x) = A_{even}(x^2) + A_{odd}(x^2) \cdot x$
Complexity: $O(|X|)$

Then the time complexity will be:
$$
T(n, |X|) = 2 * T(n/2, |X|) + O(n + |X|)
$$
For efficient sampling, $|X|$ should be $n$. Thus, according to master theory, the total complexity should be $O(n^2)$.

> Why? $O(n)$ nodes in divide tree, $O(n + |X|) = O(n)$ for each node.
>
Can we do better?

### Find $X$ that collapses

In the divide step, we uses $x^2$ for recursive steps. Can we find such $X$ s.t. $X' = \{x^2 \ | \ x \in X\}$ and $|X'| = \frac{|X|}{2}$ or $|X'| = |X| = 1$?

The answer is yes - let's find them out!

$$
\begin{align}
|X| &= 1 \rightarrow X = \{ 1 \}\\
|X| &= 2 \rightarrow X = \{ 1, -1\}\\
|X| &= 4 \rightarrow X = \{ 1, -1, i, -i\}\\
|X| &= 8 \rightarrow X = \{ 1, -1, i, -i, \pm \frac{\sqrt{2}}{2}(1 + i), , \pm \frac{\sqrt{2}}{2}(1 - i)\}\\
\end{align}
$$

As you might notice, if $|X_k| = 2^k$, then $|X_k| = \{\pm\sqrt{x} \ | \ x \in X_k-1\} \ \forall k \in \mathbb{N}$

### Time Complexity
Then the complexity will be:
$$
n \cdot 1 + \frac{n}{2} \cdot 2 + \cdots + \frac{n}{2^{n-1}} \cdot 2^{n-1} + 1 \cdot n = O(n \log_2 n)
$$
Or:
$$
T(n, |X|) = 2 * T(\frac{n}{2}, |X| \cdot 2) + O(n + |X|)
$$
Initially $|X|$ is $1$.

How to find $X$ fast? Geometry!

## Computing $X$

On the complex plane, we can denote all $x$ as:
$$
\begin{align}
&(\cos \theta, \sin \theta) \\
&= \cos \theta + i \sin \theta \\
&= e^{i \theta}
& \forall \theta \in \{ 0, \frac{\tau}{n}, \frac{2\tau}{n}, \cdots, \frac{(n-1)}{n}\tau\} \\
&= e^{i \tau \frac{k}{n}}
& \forall k \in \{0, 1, \cdots, n-1\}
\end{align}
$$
Where $\tau = 2 \pi$.

Then, $\sqrt{x}$ should be:
$$
\begin{align}
& \sqrt{e^{i \theta}} \\
&= e^{\frac{1}{2} i \theta} \\
&= e^{i (\frac{1}{2} \theta)} \\
&= \cos \frac{\theta}{2} +i \sin \frac{\theta}{2}
& \forall \theta \in \{ 0, \frac{\tau}{n}, \frac{2\tau}{n}, \cdots, \frac{(n-1)}{n}\tau\}
\end{align}
$$

So we can iterate through all $\theta$ in $O(n)$ time.
This can be done by precalculating with `<cmath>` and `<complex>` in C++.

## Multiplying Two Polynomials

Let's calculate $A * B$ where $A, B$ are two polynomials:

1. $A' = FFT(A)$
2. $B' = FFT(B)$
3. $C'_k = A'_k \cdot B'_k$
4. $C = IFFT(C')$

Note: `IFFT` stands for `Inverse FFT`.

So the last question is: how to do the inverse?

## Inverse FFT

Let's go back to $V$.

$$
V_{jk} = x_j^k,\
V = \begin{bmatrix}
x_0^0 & x_0^1 & x_0^2 & \cdots & x_0^{n-1}\\
x_1^0 & x_1^1 & x_1^2 & \cdots & x_1^{n-1}\\
x_2^0 & x_2^1 & x_2^2 & \cdots & x_2^{n-1}\\
\vdots & \vdots & \vdots & \vdots & \vdots & \\
x_{n-1}^0 & x_{n-1}^1 & x_{n-1}^2 & \cdots & x_{n-1}^{n-1}
\end{bmatrix}
$$

And we know

$$
\{x_0, x_1, x_2, \cdots, x_{n-1}\}
= \{ e^{0i \frac{\tau}{n}}, e^{1i \frac{\tau}{n}}, e^{2i \frac{\tau}{n}}, \cdots, e^{(n-1)i \frac{\tau}{n}} \}
$$

Then:

$$
V_{jk} = \omega_j^k = e^{ijk \frac{\tau}{n}}
$$

The inverse transform would be: $V^{-1}A' = A$

### Claim: $V^{-1} = \frac{1}{n} \bar V$
**Proof:**

$$
\begin{align}
& V \cdot \bar V \\
&= \sum_{m = 0}^{n - 1} { e^{ij \tau \frac{m}{n}} \cdot e^{-im \tau \frac{k}{n}}} \\
&= \sum_{m = 0}^{n - 1} { e^{i \tau \frac{m}{n}(j - k)} }
\end{align}
$$

If $j \neq k$:
$$
\begin{align}
& \sum_{m = 0}^{n - 1} { e^{i \tau \frac{m}{n}(j - k)} }\\
&= \sum_{m = 0}^{n - 1} { (e^{i \tau \frac{(j - k)}{n}})^m }\\
&= \frac{ (e^{i \tau \frac{(j - k)}{n}})^n - 1}{e^{i \tau \frac{(j - k)}{n}} - 1}\\
&= \frac{ e^{i \tau (j - k)} - 1}{e^{i \tau \frac{(j - k)}{n}} - 1}\\
& \because e^{i \tau} = 1, (j - k) \in \mathbb{Z}\\
& \therefore e^{i \tau (j - k)} = 1 \rightarrow \frac{ e^{i \tau (j - k)} - 1}{e^{i \tau \frac{(j - k)}{n}} - 1} = 0
\end{align}
$$

If $j = k$:
$$
\begin{align}
& \sum_{m = 0}^{n - 1} { e^{i \tau \frac{m}{n}(j - k)} }\\
&= \sum_{m = 0}^{n - 1}{ e^0 }\\
&= n
\end{align}
$$

Thus, $V \cdot \bar V = n \cdot I , \ V^{-1} = \frac{1}{n} \bar V \ \ \blacksquare$

## Cooley-Tukey FFT Algorithm

## Number Theoretic Transform NTT

Another way of collapsing $|X|$
Fermat's Little Theorem
Chinese Remainder Theorem
FFT v.s. NTT

## Problems

- [Kattis A+B Problem](https://open.kattis.com/problems/aplusb)
- [CodeForces 528D Fuzzy Search](https://codeforces.com/problemset/problem/528/D)
- [TIOJ 1035 通關密語](https://tioj.ck.tp.edu.tw/problems/1035)
- [OJDL 7060 幫幫DZ](https://ojdl.ck.tp.edu.tw/problem/7090)
- BigInt multiplier, ex. [TIOJ 1064 A\*B Problem](https://tioj.ck.tp.edu.tw/problems/1064)