mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2003-05-28, 06:13   #1
1260
 
Feb 2003

25 Posts
Default Faster way to do LLT?

As I understand it, everytime the LLT is done to M(n), computation starts from S(1) mod M(n) up to S(n-1) mod M(n).

Suppose, if the unMODed value of S(n-1) is saved so that it can be used for the next possible candidates and MODed to M(n+k), wouldn't it be faster?

I know that S(n-1) can be extremely large in comparison to M(n), but does using more hard disk space compensate for the time spent in re-computing from S(1)?
1260 is offline   Reply With Quote
Old 2003-05-28, 07:23   #2
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

Well, I'm not a mathematician, but I think one of the reasons that it must be MODed is this :

The LL Formula always squares the result of the previous iteration (and minus 2, but this is negligable). Considering the current ranges we are testing it is impossible to store such large numbers.

Just start with the S(0) = 4 value and try to square it just 1 million times (and we are currently testing at almost 20 million). You'll see that you'll need WAAAAAAY more space than the largest hard drives or industrial data storage drives on earth. It is therefor impossible to store them.

Axel Fox.
Axel Fox is offline   Reply With Quote
Old 2003-05-28, 15:40   #3
jocelynl
 
Sep 2002

2·131 Posts
Default

In LL test S(n) increases very fast. So it would be useless to store the first few. Imagine 2 squared then 4,16,256,65536, etc... 2^1,2^2,2^4,2^8,2^16,2^32... so it takes no time to reach 2^M-1.
And theses are computed much faster than retreiving it from a disk.


Joss.
jocelynl is offline   Reply With Quote
Old 2003-05-28, 18:52   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default Re: Faster way to do LLT?

Quote:
I know that S(n-1) can be extremely large in comparison to M(n),
It's not always appreciated just how large the unMODed S(i) values get.

The estimated total number of particles (electrons, proton, neutrons, muons, ...) in the known universe is less than 10^100. 10^100 is less than 2^400. If we could use every particle in the universe to store one binary bit, the largest number we could store would be less than 2^(2^400).

Let's look at the unMODed S(i) values:

S(1) = 4 = 2^2

S(2) = (2^2)^2 - 1 = 2^4 - 1 > 2^3

S(3) > (2^3)^2 - 1 > 2^5

S(4) > (2^5)^2 -1 > 2^9

...

For k > 1, S(k) > 2^(2^(k-1)+1)

So S(1000) > 2^(2^999 + 1), which is already way, way above the "universal" storage limit.

And S(1000) isn't very far along the path toward S(several-million).

Edit: I just found an estimate that if the known universe (which is mostly empty space) were packed solid with neutrons (which can be packed more tightly together than other types of particle), it would take 10^128 neutrons. Let's be generous and say it took 10^200 neutrons. 10^200 is less than 2^800. S(1000) still wouldn't fit.

It's not a matter of using more hard disk space. :)
cheesehead is offline   Reply With Quote
Old 2003-05-28, 18:55   #5
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

Woooooow, the unMODed LL function raises THAT quickly ???

I don't know what you all think of this post, but I think it's a neat thing to know.
Axel Fox is offline   Reply With Quote
Old 2003-05-29, 02:33   #6
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×3×1,193 Posts
Default

Quote:
Originally Posted by Axel Fox
Considering the current ranges we are testing it is impossible to store such large numbers.
Amen. If every proton, neutron, and electron in the universe could store one bit of the S(n) value you wouldn't come close to enough storage space.


Oops, someone beat me to the punch in pointing this out!
Prime95 is offline   Reply With Quote
Old 2003-05-29, 07:47   #7
1260
 
Feb 2003

25 Posts
Default

Okay. If it is really THAT LARGE, isn't there a mathematical conversion to do something similar?

I mean, if S(n-1) = A mod M(n) = B mod M(n+k), then computation can start from S(n-1) to S(n-1+k) for M(n+k) which would be shorter. Is it then possible to solve for B from A, M(n) and M(n+k)?

If not, maybe more values might help:
if S = A mod M(n+a) = B mod M(n+b) = C mod M(n+c) = D mod M(n+d), where a<b<c<d, can D be computed from A, B, and C?

I'm not really familiar with all the theorems in modular arithmetic involving a change of modulo. Is there one related to this problem?

By the way, is the remainder of S(n-1) mod M(n) saved in the results.txt file? Which is it, the Res64 or the WY1?
1260 is offline   Reply With Quote
Old 2003-05-29, 12:28   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by 1260
Okay. If it is really THAT LARGE, isn't there a mathematical conversion to do something similar?
The world of math will thank you if you can find a shortcut (shorter than L-L, that is), and you can even win a cash prize offered by George/GIMPS. But lots of folks have already tried.

Quote:
I mean, if S(n-1) = A mod M(n) = B mod M(n+k), then computation can start from S(n-1) to S(n-1+k) for M(n+k) which would be shorter. Is it then possible to solve for B from A, M(n) and M(n+k)?
Yes, but it takes at least as much computation as the straight L-L method, so is not a shortcut.

The catch is that the mod M(n) has been performed on every S(i) value up to S(n-1). That is, there have been a string of up to n-2 divisions by M(n) performed in order to reach the S(n-1) value. If we're going to re-use the S(n-1) value for M(n+K), all of those divisisons would have to be replaced by divisions by M(n+k). Since divisions by M(n+k) produce different remainders than divisions by M(n), this becomes equivalent to re-calculating all the S(i) mod M(n+k) up to S(n-1), then continuing to S(n+k-1). IOW, we'll have to recalculate all the S(i) in mod M(n+k) anyway.

Quote:
If not, maybe more values might help:
if S = A mod M(n+a) = B mod M(n+b) = C mod M(n+c) = D mod M(n+d), where a<b<c<d, can D be computed from A, B, and C?
Struggle as one might, as far as anyone has yet determined all such attempted shortcuts wind up having to do at least as much computation as the straight L-L method.

Quote:
By the way, is the remainder of S(n-1) mod M(n) saved in the results.txt file? Which is it, the Res64 or the WY1?
The low-order (right-hand) 64 bits of S(n-1) mod M(n) are saved as the Res64.
cheesehead is offline   Reply With Quote
Old 2003-06-07, 21:30   #9
clowns789
 
clowns789's Avatar
 
Jun 2003
The Computer

3×127 Posts
Default

Perhaps you can have something similar to Prime95 that guesses that stuff up.
clowns789 is offline   Reply With Quote
Old 2003-09-29, 14:04   #10
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

I believe there is a way to leverage some of the effort of computing a LL sequence for two different numbers under test:

By example I will show the LL sequences for 2^5-1 and 2^7-1 followed by a sequence that attempts to combine some of the work.

Testing 2^5-1, the LL sequence is:
S(0)= 4
S(1)= 4^2 - 2 mod 31 = 14
S(2)=14^2 - 2 mod 31 = 8
S(3)= 8^2 - 2 mod 31 = 0 ; therefore 2^5-1 is prime

Testing 2^7-1, the LL sequence is:
S(0)=4
S(1)= 4^2 - 2 mod 127 =14
S(2)= 14^2 - 2 mod 127 =67
S(3)= 67^2 - 2 mod 127 =42
S(4)= 42^2 - 2 mod 127 =111
S(5)=111^2 - 2 mod 127 =0 ; therefore 2^7-1 is prime

Testing both 2^5-1 and 2^7-1, the LL sequence is:
S(0)=4
S(1)=4^2 - 2 mod (31*127) = 14
S(2)=14^2-2 mod (31*127) = 194
S(3)=194^2-2 mod (31*127) = 2201
at this step,
2201 mod 31=0 therefore 2^5-1 is prime
continue the sequence using
2201 mod 127=42
S(4)=42^2-2 mod 127= 111
S(5)=111^2-2 mod 127=0 ; therefore 2^7-1 is prime
only_human is offline   Reply With Quote
Old 2003-09-29, 14:57   #11
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

EAA16 Posts
Default

In the message that I posted above, I'd known that since the intermediate values would be computed modulo a value involving maybe twice as many bits, each squared value would be perhaps four times as large as a ordinary LL sequence value.

Another detraction that didn't occur to me so quickly is that the modulo step would no longer be involving a value one less than a power of two. So it might require a true divide rather than anything like convenient method currently used.

Last fiddled with by only_human on 2003-09-29 at 14:59
only_human is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
faster than LL? paulunderwood Miscellaneous Math 13 2016-08-02 00:05
Is it faster to run 1 worker or many? arbiter21 Information & Answers 17 2016-02-05 05:04
My CPU is getting faster and faster ;-) lidocorc Software 2 2008-11-08 09:26
3-PRP faster than LL for GIMPS? bearnol Math 35 2005-10-12 14:33
Faster than LL? clowns789 Miscellaneous Math 3 2004-05-27 23:39

All times are UTC. The time now is 22:34.

Sat Sep 26 22:34:19 UTC 2020 up 16 days, 19:45, 0 users, load averages: 1.29, 1.42, 1.49

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.