The set of S tier (Superlative) inventions is not so big, and two of the best things ever to be invented by humanity are Fourier transform (FT) and his Fast version, the Fast Fourier Transform (FFT). It is such a fantastic and useful thing that every time I encounter it, it fills me with joy and awe for the great mystery that is mathematics. FT is a fundamental tool of mathematics, and doing it fast is something incredibly useful.
No problem this is a small review on how FFT works. Here are some simple c scripts that do discrete FT and fast FT. I would like to specify that these programs are made for didactic reasons, and because of dynamical memory allocation are very dangerous and slow. A real program would need bit reversal algorithm , like this bit reversal FFT, and it is best to use a library program for the FFT (in C or python). In the following table you can get an idea of the speed up we are talking about, and how the professional libraries are far superior. I also tried to make an optimized version of my program using LLM model "gemini Pro 3.1", it provided a slightly faster version than mine own.
| N | DFT naive(ft.c) | FFT recursive (fft.c) | FFT bit reversal (fft_bit_rev.c) | FFT made by gemini Pro 3.1 | FFTW3 (Library FFT) |
|---|---|---|---|---|---|
| 256 | 1.6456 ms | 0.0225 ms | 0.0072 ms | 0.0044 ms | 0.0011 ms |
| 512 | 6.2565 ms | 0.0613 ms | 0.0163 ms | 0.0096 ms | 0.0015 ms |
| 1024 | 25.8308 ms | 0.1280 ms | 0.0356 ms | 0.0208 ms | 0.0028 ms |
| 2048 | 103.4527 ms | 0.2703 ms | 0.0768 ms | 0.0459 ms | 0.0058 ms |
| 4096 | 393.7990 ms | 0.5841 ms | 0.1676 ms | 0.1003 ms | 0.0158 ms |
| 8192 | 1575.2290 ms | 1.3467 ms | 0.3599 ms | 0.2277 ms | 0.0384 ms |
Thanks for the attention, Aug. 2026, Rome, Tommaso Virgilii.