red_coder's blog

FFT implementation !!!
By red_coder, 12 years ago, In English

hey guys! today i learnt about FAST FOURIER TRANSFORM but i have no idea of how to implement this nice algorithm in c++ code. When i tried to search for the code in google all i got was a set of codes implementing it not directly but in one form or the other. So i am totally messed up.....

Guys suppose we are given two polynomial coeffecients each of degree N in vector form P and Q. Please can anyone write a nice C++ code with comments for multiplying these polynomials and output a vector of size 2N denoting the coeffecients of the resulting polynomial (product of Polynomials P and Q). Thanks in advance.

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

»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I've wrote an article about it one day, you can try use Google Translate or just get some code examples from.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    not good, google translate doesnot work good, the translated article is not clearly understandable , any resource you can give in english??

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

      google translate doesnot work good

      I've checked the article translation with Google Translate and I confirm that the translation is very decent and clear enough.

      Which fragments you could not understand?

      Or provide a link at any chosen source you've found with "fft implementation with comments" search query and point which statements or paragraphs look troublesome to you?

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

    now got it, thanks a lot :)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    hey i tried to use ur code but its giving runtime-error, can u figure out the problem, here is my CODE

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why it is necessary to use auxiliary array? We can do it inplace.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I forgot it when I write this article. Yes, we can and this is one more place to optimize.

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

I guess this will help: FFT(c++)MITnotebook

→ Reply