onlydmc123's blog

Fast Fourier Transform, Multiplying Polynomials , Need Help
By onlydmc123, 10 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

mamba chi ha mamba chi ???

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From my library: http://ideone.com/tbHUN7

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that complex<> is slow. It's better to use hand-written struct.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply