I want to know how to implement FFT for real inputs not a power of 2.can somebody provide me a tutorial.
I’ve implemented Cooley-Tukey.For odd, but still I’m getting wrong answer.
You can use Bluestein’s algorithm.
I guess one had to apply Number Theoretic Transform.Can somebody show me some implementation.I read it somewhere that it takes care of the overflow error.
For tutorial of NTT and FFT for non powers of 2:
you can see this link’s answer : https://discuss.codechef.com/questions/82993/workchef-and-polyeval-problems-in-july-16
Also for detailed understanding for non power of 2 composite numbers , you can take help of this pdf:
In case of prime fields, you can use bluestein’s algorithm or radar’s algorithm(which is almost similar to NTT)
yes , you are right…NTT takes care of overflow errors. One of implementation is in this code where you can see the FFT function in which NTT is used
The function is for powers of 2. Also the g in the function is generator. Detailed explanation of NTT:
why dont you add zeros to the polynomial , until it becomes a power of 2. by this method you wont add more than n zeros . so thats cool i guess .
I guess this method which is not exactly accurate and gives wrong answer in many questions:https://discuss.codechef.com/questions/31836/realset-editorial
You may see this answer by mugurelionot in the above page:
I looked at your implementation and your algorithm is not correct.You can only use the Radix2 Cooley Tukey FFT algorithm when N is a power of 2.When N is odd you split the array into two slices of unequal sizes.You probably make them equal by adding an extra zero coefficient in the smaller slice,but that is incorrect and the end result is not the FFT for the initial array of N values.
but thats really one of the standard approaches i guess !
Well suppose your N=N1xN2xN3 where N1,N2 and N3 are primes. You can divide your polynomial like this
A(y) = A0(y^N1) + y*A1(y^N1) + (y^2)A2(y^N1) + … + (y^N1-1)*A(N1-1)(y^N1)
where each of the polynomials A0,A1,A2 A(N1-1)are or degree N2xN3.
Now again divide each of your polynomial A to A(N1-1) into N2 polynomials each of degree N3 in similar fashion. If you are asking with respect to the question POLYEVAL then N=786432=3*(2^18)
where each of your polynomials A0,A1 and A2 are of degree 2^18. So you can use standard(radix 2) FFT for these (A0,A1 and A2) since their degree is power of two.
If you have are given polynomial like this
g(y) = a0 + a1y + a2(y^2)
and your N=786432 and then make it a polynomial of degree 786432 by appending zeroes (simple)
g’(y) = a0 + a1y + a2(y^2) + 0*(y^3) + … + 0*(y^N)