Recently i have seen a lot of questions being asked on fast fourier transforms. I have tried to read and understand it from T. cormen’s book(Introduction to algorithms) but i think it requires some other concepts of mathematics too and thus i was unable to proceed.Can anyone please tell me what are the prerequisities before learning fast fourier transforms?
In Coreman, the explanation about the topic is sufficient enough to implement FFT, as it covers the required mathematics. Try reading it few times, you’ll get clear understanding how the property of complex roots is utilized to yield 0(nlogn) time. If you still struggle then try reading about complex numbers and roots of unity (just basic required).
For implementation in C++ you can use Complex data type, also check out other people submissions and see how they have implemented.
You can read it more about it on link text, its in Russian, use google translate or Yandex Translator.
1 Like
The pre-requisites for learning FFT are:
- N^{th} Principal root of unity
- Groups and Fields
- Polynomials
1 Like
You just have to know polynomials and a bit of matrices.Got to youtube search for mit ocw 6.046 lectures and there is one lecture on FFT ( I think under divide and conquer).It is quite easy to understand(well, relatively atleast.)
1 Like