how to make fast fourier transform in excel

FAST FOURIER TRANSFORM (FFT) ALGORITHMS

The term fast Fourier transform (FFT) refers to an efficient implementation of the discrete Fourier transform (DFT) for highly composite transform lengths . When computing the DFT as a set of  inner products of length  each, the computational complexity is . When  is an integer power of 2, a Cooley-Tukey FFT algorithm delivers complexity , where  denotes the log-base-2 of , and  means ``on the order of ''.

Such FFT algorithms were evidently first used by Gauss in 1805  and rediscovered in the 1960s by Cooley and Tukey

DFT is a linear transform which takes as input a complex signal x of length N and gives as output a complex signal X of length N, X=Wx. W is a complex NxN matrix with entiries W_k,n=exp(-2pi*k*n/N), where 0untill k, n unitll N. DCT is a linear transform which takes as input a real signal x of length N and gives as output a real signal X of length N. It is computed by taking DFT of the signal y of length 2*N which is the concatenation of the signal with its reverse, that is y={x[0],...x[N-1],x[N-1],...,x[0] }. Since y is symmetric its DFT is real. FFT is a collection of algorithms for fast computation of the DFT. Typically the number of operations required by the FFT is on the order of N*logN. The most famous FFT algorithms are for the case that N is a power of 2, but there are FFT for prime orders and for different other factorizations.

https://youtu.be/xf_RnnuPa-c