mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2008-09-05, 15:47   #1
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Default 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
nuggetprime is offline   Reply With Quote
Old 2008-09-05, 18:02   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×4,919 Posts
Default

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

Last fiddled with by ewmayer on 2008-09-05 at 18:02
ewmayer is online now   Reply With Quote
Old 2008-09-05, 23:29   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

... in the Math subforum. Start at its post #5.
cheesehead is offline   Reply With Quote
Old 2008-09-05, 23:58   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,159 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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
Prime95 is offline   Reply With Quote
Old 2008-09-06, 10:03   #5
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Default

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
nuggetprime is offline   Reply With Quote
Old 2008-09-06, 13:29   #6
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

157678 Posts
Default

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

It explains IBDWT in an all-integer FFT.
Prime95 is offline   Reply With Quote
Old 2008-09-07, 14:08   #7
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Default

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

Thanks,
nuggetprime
nuggetprime is offline   Reply With Quote
Old 2008-09-08, 17:41   #8
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

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

Thanks,
nuggetprime
nuggetprime is offline   Reply With Quote
Old 2008-09-09, 14:01   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66418 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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.
jasonp is offline   Reply With Quote
Old 2008-09-10, 15:19   #10
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

4568 Posts
Default

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 is offline   Reply With Quote
Old 2008-09-10, 17:32   #11
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

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
nuggetprime is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 20:59.

Mon Nov 30 20:59:26 UTC 2020 up 81 days, 18:10, 2 users, load averages: 2.54, 2.42, 2.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.