Questions on coding my FFT&LLR implementation
 

I know that there is a fft-thread in this forum, but it's still to hard for me. I'm currently coding an implementation of the LLR(Lucas-lehmer-riesel) test.It's currently using the GMP and I want to implement FFT for it. Can you please explain me the way from the x^2 calculation(I think that's the point where FFT helps) to the FFT. Also,if possible,can you show me an example on a small mersenne number(LL test)? This might help me a lot in understanding.

Thanks,
nuggetprime

Search for the thread titled "FFT explanation for non math guys".

... in the Math subforum. Start at its post #5.

[QUOTE=ewmayer;140990]Search for the thread titled "FFT explanation for non math guys".[/QUOTE]


I stickied it as it was hard to find and is asked for several times a year

Thanks,I'm now understanding DFT in basics.
How does then the IBDWT work(different)? There aren't many resources on the web to this.

Thanks,
--nugget

Look at [url]http://www.mersenne.org/intfft.txt[/url]

It explains IBDWT in an all-integer FFT.

Question: What's the best way to store the transformed numbers? floating point,or?

Thanks,
nuggetprime

Otherwise formulated:is double enough for,say, FFT length 500K?

Thanks,
nuggetprime

[QUOTE=nuggetprime;141463]Otherwise formulated:is double enough for,say, FFT length 500K?
[/QUOTE]
Yes, double precision should be plenty. It may be just insufficient if you are not careful with how you generate the trig factors for the FFT; references often use a recursion for them which causes increased roundoff error for very long transform lengths.

Thank you for your answer jasonp.
But how can I calculate in binary in C?
I probably will have to create arrays of 1-bit fields,or?

Thanks,
nugget

The above was not stated precisely, I think.
I want to know if in C, when i define a ,say, unsigned short int, how can I access a certain bit of it,in reasonable CPU time?
Thanks,
--nuggetprime