[Tutorial] Linear Time FFT

Revision en5, by TheBhediyaOfDalalStreet, 2023-02-19 20:16:17

Hell guys, today I gonna teach you to do linear time FFT.

Below is the problem:

Q) Given array of n integers, do First Four Traversal on array.

eg. array is [1, 2, 3, 4, 5, 6, 2, 1], then FFT of array is [1, 2, 3, 4].


So in first, it look very dangerous problem, but on meticulous scrutiny of the underlying scheme, we find easy solution.

  • So to solve, we iterate over the array from left to right. While left to right is happening, store first 5 elements of array in an array x[5] = [1, 2, 3, 4, 5].

For those thinking why 5, there is actually a very high IQ reason behind it. So maybe not everyone get it, so I not telling it in this blog.

  • Now what we are gonna doing is, we are find the circular-convolution of the array with itself, xc = x[0:5] ⋆ x[0:5]. This is the very easy technique, so I hope all will be able to find auto-circular convolution.

For up example, xc[5] = [45, 50, 50, 45, 355].

  • Now we will using the easy technique: Discrete Fourier Transform (DFT) to calculate X(5) of xc[5]. This step is easy so I am skip

  • Next we can find the square root of X(5) and take the inverse DFT of the sequence i[5].

  • Then we can simply print the first 4 element of i[5].

For those thinking why 4, there is actually a very high IQ reason behind it. So maybe not everyone get it, so I not telling it in this blog.

Prove of algorithm: Got same output. Hence proofed.

Time complexity analysis: Linear

Tags fft, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English TheBhediyaOfDalalStreet 2023-02-24 07:45:16 0 (published)
en5 English TheBhediyaOfDalalStreet 2023-02-19 20:16:17 22
en4 English TheBhediyaOfDalalStreet 2023-02-17 19:19:26 6 Tiny change: 'ay xc = x[5] * x[5]. This i' -> 'ay xc = x[0:5] ⋆ x[0:5]. This i'
en3 English TheBhediyaOfDalalStreet 2023-02-17 19:15:09 61
en2 English TheBhediyaOfDalalStreet 2023-02-16 17:19:10 956 Tiny change: 'his blog._' -> 'his blog._\n\nTime complexity analysis: Linear'
en1 English TheBhediyaOfDalalStreet 2023-02-14 20:15:30 465 Initial revision (saved to drafts)