mersenneforum.org Questions on coding my FFT&LLR implementation
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-05, 15:47 #1 nuggetprime     Mar 2007 Austria 1001011102 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 ∂2ω=0     Sep 2002 República de California 9,791 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-05, 23:29 #3 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×599 Posts ... in the Math subforum. Start at its post #5.
2008-09-05, 23:58   #4
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

157418 Posts

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

 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 32×13×61 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 1001011102 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 2×151 Posts Otherwise formulated:is double enough for,say, FFT length 500K? Thanks, nuggetprime
2008-09-09, 14:01   #9
jasonp
Tribal Bullet

Oct 2004

66418 Posts

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.

 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
 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 jrafanelli Software 2 2018-01-11 15:16 kelzo Programming 3 2016-11-27 05:16 flouran Programming 0 2009-07-25 02:43 starrynte Programming 1 2008-12-30 22:31 R.D. Silverman Programming 18 2005-08-09 13:14

All times are UTC. The time now is 01:24.

Sat Oct 24 01:24:23 UTC 2020 up 43 days, 22:35, 0 users, load averages: 1.36, 1.30, 1.26