I was searching a lot to understand FFT, I know FFT has many applications, but I need it for multiplying polynomials. I Found this: http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt. and it was really helpful to understand its nature, there is given algorithm in pseudo-C too, but I don't know how to implement it in C or C++. Can you suggest to me clean impelementation of FFT, where the inputs are two polynomials and output is multiplication of them?
Thanks in advance.
mamba chi ha mamba chi ???
What was the goal of this stupid comment?
He said that "It doesn't concern me"
From my library: http://ideone.com/tbHUN7
Note that
complex<>is slow. It's better to use hand-written struct.I recently learned FFT myself. For theory I read CLRS. It has a whole chapter on the topic. For implementation I used http://e-maxx.ru/algo/fft_multiply. I used the implementation to get AC in UVa 12879 — Golf Bot.
This is my C++ program https://ideone.com/jR993P, that is quite complete except enter 2 input polynomials ( this for you ). I hope that can help you