# 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)