FFT - The tough made simple

This is a 2-post article explaining what is FFT (Fast Fourier Transform) and how FFT & NTT work.

This was originally written by me 2 years ago on CodeForces platform.

Since I intend to seriously start blogging, therefore I am attaching the PDFs and sharing the original links of this previous article. I am not porting the original blog because it was written in HTML + Latex whereas this website as of now supports Markdown + Latex only, so editing the entire article would turn out to be an unnecessary and time - consuming task.

Any kind of feedback would be appreciated :)

FFT 1 - PDF

FFT 1 - Codeforces

FFT 2 - PDF

FFT 2 - Codeforces

Written on July 29, 2018