0

So far I managed to run the FFT and I got the next table of coefficients:

[2, 1 + i, 0, 1 - i, 2, 1 + i, 0, 1 - i]

The problem I have is to compute the inverse and get the polynomial in its coefficient form. Can you please help me by explaining how to determine the inverse of the root of the unity that I need to use? And a more broad explanation of how to apply IFFT.

Thank you a lot!

Mark
  • 253
  • 1
  • 5
  • 22
  • I disagree, it's an algorithmic question, I am asking for an explanation on how to do the IFFT algorithm, including some math points that I didn't understand while reading about it. – Mark Jul 04 '15 at 23:03
  • What language are you using? if you were able to perform a forward FFT then performing an IFFT should be easy. – KillaKem Jul 05 '15 at 09:31
  • At the moment I am trying to solve it just on papaer, but I have FFT written in Java. – Mark Jul 05 '15 at 10:05
  • possible duplicate of [FFT for equations that have terms with different exponents](http://stackoverflow.com/questions/18940422/fft-for-equations-that-have-terms-with-different-exponents) – Spektre Jul 05 '15 at 21:14

1 Answers1

1

what exactly you want to use FFT/IFFT for?

  1. if x is a bignum

    • see fast bignum sqr especially Schönhage-Strassen multiplication
    • for ^2 and ^3 you can compute NTT/FFT just once instead of 2 and 3 times

  2. x^2+1 is polynomial

[Notes]

  • for both cases is use of NTT instead of FFT much better
  • due to precision loss (rounding errors)
Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • I use it for multiplication of polynomials, but the question is about the tiny details with the roots of the unity, I don't know how to determine those. The provided link tells me everything that I already know. – Mark Jul 05 '15 at 21:30
  • 1
    @Mark if you use custom root of unity (on finite field) then you are performing NTT not FFT !!! see the NTT link . does not matter which modulo prime you choose but it must be bigger then any of the sub-results (coefficients) I am using the max unsigned 32bit prime available `0xC0000001` The root of unity and its inverse is tricky I wrote a program that search whole 32bit range and test for all needed condition and the result is in the NTT link source code member function `bool fourier_NTT::init(DWORD n)` – Spektre Jul 05 '15 at 21:38
  • Thank you! I will take a look and if I don't manage my way out will comment here – Mark Jul 05 '15 at 21:46