Inverse Fast Fourier Transform

The Inverse Fast Fourier Transform is an algorithm that finds a polynomial $f(x)={\sum }_{i=0}^{n-1}{a}_i{x}^i$ such that $\forall k\in \{0,1,\dots ,n-1\},f({\omega }_n^k)=b_k$, if $\exists k\in \mathbb{N},n=2^k$, in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

Let

$$g(x)=\sum _{i=0}^{n-1}{b}_i{x}^i$$

then

$$f(x)=\frac{1}{n}\sum _{i=0}^{n-1}g({\omega }_n^{-i})x^i$$

is a polynomial such that $\forall k\in \{0,1,\dots ,n-1\},f({\omega }_n^k)=b_k$.

Proof

Lemma

$$\forall n\in {\mathbb{Z}}_{+},\forall k\in \mathbb{Z},[n\mid k]=\frac{1}{n}\sum _{i=0}^{n-1}{\omega }_n^{ki}$$

Proof

• If $n\mid k$,

  $$\begin{array}{rl}\frac{1}{n}\sum _{i=0}^{n-1}{\omega }_n^{ki}& =\frac{1}{n}\sum _{i=0}^{n-1}1\\ & =1\end{array}$$

• If $n\nmid k$,

  $$\begin{array}{rl}\frac{1}{n}\sum _{i=0}^{n-1}{\omega }_n^{ki}& =\frac{{\omega }_n^{kn}-1}{n({\omega }_n^k-1)}\\ & =0\end{array}$$

$$\begin{array}{rl}f({\omega }_n^k)& =\frac{1}{n}\sum _{i=0}^{n-1}g({\omega }_n^{-i}){\omega }_n^{ki}\\ & =\frac{1}{n}\sum _{i=0}^{n-1}{\omega }_n^{ki}\sum _{j=0}^{n-1}{b}_j{\omega }_n^{-ij}\\ & =\frac{1}{n}\sum _{j=0}^{n-1}{b}_j\sum _{i=0}^{n-1}{\omega }_n^{i(k-j)}\\ & =\sum _{j=0}^{n-1}[n\mid k-j]b_j\\ & =b_k\end{array}$$

0. Apply the Fast Fourier Transform to find $g({\omega }_n^0),g({\omega }_n^1),\dots ,g({\omega }_n^{n-1})$.
1. Apply the lemma to find $f$.

This algorithm solves the problem in $\mathcal{O}(n\log n)$ time and $\mathcal{O}(1)$ space.

void ifft(int n, std::vector<std::complex<double>> &a) {
	fft(n, a);
	std::ranges::reverse(a | std::views::drop(1));
	for (int i = 0; i < n; i++) {
		a[i] /= n;
	}
}