stefanbalaz2's blog

Question about multiplying complex polynomials with FFT
By stefanbalaz2, history, 3 years ago, In English

Is there a way to multiply 2 polynomials with complex coefficients by using only 1 FFT and 1 inverse FFT?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you want to calc $$$f(x) * g(x)$$$, you can simply calc $$$(f(x) + g(x)i)^2=f(x)^2 - g(x)^2 +2f(x)g(x)i$$$.

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

    How does that help? f(x)^2-g(x)^2 doesn't have to be real, so how would you extract that part and the part f(x)g(x)? Secondly, squaring is also a multiplication, so your oracle for multiplication uses multiplication...

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

      Squaring can be done in one FFT and one IFFT.

      I think that what Rosetxdy means is that if f(x) and g(x) have real coefficients, you can construct (f(x)+ig(x)), square it, and extract the complex part for the answer. I'm not aware of any method to multiply polynomials with non-real coefficients in only 1 FFT and IFFT.

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

      This's my ancient code.:)

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

    Isn't $$$(f(x) + g(x)i)^2 = f(x)^2 - g(x)^2 + 2f(x)g(x)i$$$? I plugged into wolfram alpha :clown:

    → Reply