Questions on coding my FFT&LLR implementation

nuggetprime · 2008-09-05, 15:47

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

ewmayer · 2008-09-05, 18:02

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

cheesehead · 2008-09-05, 23:29

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

Prime95 · 2008-09-05, 23:58

Quote:

Originally Posted by ewmayer

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

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

nuggetprime · 2008-09-06, 10:03

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

Prime95 · 2008-09-06, 13:29

Look at http://www.mersenne.org/intfft.txt

It explains IBDWT in an all-integer FFT.

nuggetprime · 2008-09-07, 14:08

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

Thanks,
nuggetprime

nuggetprime · 2008-09-08, 17:41

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

Thanks,
nuggetprime

jasonp · 2008-09-09, 14:01

Quote:

Originally Posted by nuggetprime

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

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.

nuggetprime · 2008-09-10, 15:19

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

nuggetprime · 2008-09-10, 17:32

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

2008-09-05, 15:47	#1
nuggetprime Mar 2007 Austria 2·151 Posts	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

2008-09-05, 18:02	#2
ewmayer ∂²ω=0 Sep 2002 República de California 103·113 Posts	Search for the thread titled "FFT explanation for non math guys". Last fiddled with by ewmayer on 2008-09-05 at 18:02

2008-09-10, 17:32	#11
nuggetprime Mar 2007 Austria 2·151 Posts	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 Last fiddled with by nuggetprime on 2008-09-10 at 17:33

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Anyone know enough about coding to do this?	jrafanelli	Software	2	2018-01-11 15:16
Python Coding Help?	kelzo	Programming	3	2016-11-27 05:16
Zhang's OPQBT coding help?	flouran	Programming	0	2009-07-25 02:43
coding midlet for TF	starrynte	Programming	1	2008-12-30 22:31
Coding Challenges	R.D. Silverman	Programming	18	2005-08-09 13:14

2008-09-05, 23:29	#3
cheesehead "Richard B. Woods" Aug 2002 Wisconsin USA 17014₈ Posts	... in the Math subforum. Start at its post #5.

2008-09-06, 10:03	#5
nuggetprime Mar 2007 Austria 2×151 Posts	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

2008-09-06, 13:29	#6
Prime95 P90 years forever! Aug 2002 Yeehaw, FL 2×53×71 Posts	Look at http://www.mersenne.org/intfft.txt It explains IBDWT in an all-integer FFT.

2008-09-07, 14:08	#7
nuggetprime Mar 2007 Austria 2·151 Posts	Question: What's the best way to store the transformed numbers? floating point,or? Thanks, nuggetprime

2008-09-08, 17:41	#8
nuggetprime Mar 2007 Austria 12E₁₆ Posts	Otherwise formulated:is double enough for,say, FFT length 500K? Thanks, nuggetprime

2008-09-10, 15:19	#10
nuggetprime Mar 2007 Austria 2×151 Posts	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