mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 3*2^n-1 Search

 
 
Thread Tools
Old 2004-09-11, 15:25   #1
scottsaxman
 
scottsaxman's Avatar
 
Aug 2004
way out west

1A16 Posts
Default fftlen change...

Could someone explain the significance of the fftlen portion of LLR? My computer had always used the Mersenne fftlen 65536. When I downloaded the 1300 range yesterday, it started using fftlen 81920 for no apparent reason. If this is appropriate, OK, but it is slower.

It still seems to be chugging along merrily, but the time/iteration is up 50%.
scottsaxman is offline  
Old 2004-09-11, 16:48   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

You can see the various 321 FFT lengths here

As our numbers get bigger and bigger we expect them to take longer and longer. A number that is twice as long as another will take over four times as long to test.

Thomas Ritschel and Jean Penne liased to form the FFT breaks. With the older LLR it would get say 90% through a number realise that the FFT size was too small and switch to a higher one -- of course the number had to be restarted with the new size. This was wasting a lot of time. HTH. I hope someone else might give a better explaination...
paulunderwood is offline  
Old 2004-09-13, 12:06   #3
Thomas11
 
Thomas11's Avatar
 
Feb 2003

5×383 Posts
Default

Quote:
Originally Posted by paulunderwood
You can see the various 321 FFT lengths here

As our numbers get bigger and bigger we expect them to take longer and longer. A number that is twice as long as another will take over four times as long to test.

Thomas Ritschel and Jean Penne liased to form the FFT breaks. With the older LLR it would get say 90% through a number realise that the FFT size was too small and switch to a higher one -- of course the number had to be restarted with the new size. This was wasting a lot of time. HTH. I hope someone else might give a better explaination...
Well, it's true that I did some modification on the FFT breaks in the older LLR, but I'm not involved in the new (faster) code and I haven't seen it's source code yet.

It seems that the new LLR/P4 uses (almost) the same algorithm for the FFT breaks as the new PRP3, for which George Woltman has given an explanation here.

If we use Georges algorithm, we get the following:
log2(3)/2 = 0.8, which leaves 19.2 bits per FFT word. Therefore the 64K FFT can handle n up to 64K*19.2 = 1258291.
In practice the switch 64K -> 80K occured at n=1273063, so it seems that the algorithm used in LLR/P4 is slightly different.
Thomas11 is offline  
Old 2004-09-13, 13:45   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

167758 Posts
Default

Each FFT length supports a different number of bits per word. Smaller FFTs support more bits per word than larger FFTs. A length 32 FFT supports about 23 bits per word, while a length 4M FFT supports about 19 bits per word.

In the current sources, if you look in mult.asm the jmptable lists the maximum Mersenne exponent each FFT length can handle. The bits per word is simply this exponent divided by the FFT length.
Prime95 is online now  
Old 2004-09-15, 13:13   #5
TTn
 

32228 Posts
Question ?

Why is the table offset from the mersenne exponents?
Is this editable?
 
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Climate Change David John Hill Jr Science & Technology 1589 2021-03-31 13:28
Name Change? Fred Lounge 8 2016-01-31 17:42
Requests for change... WraithX FactorDB 32 2014-12-18 03:40
Change the world! Xyzzy Lounge 5 2009-08-31 12:41
How can I change worktype? Andriy Information & Answers 1 2009-06-20 12:39

All times are UTC. The time now is 15:26.


Tue Nov 30 15:26:01 UTC 2021 up 130 days, 9:55, 0 users, load averages: 1.75, 1.66, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.