mersenneforum.org Faster way to do LLT?
 Register FAQ Search Today's Posts Mark Forums Read

 2003-05-28, 06:13 #1 1260   Feb 2003 2016 Posts 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)?
 2003-05-28, 07:23 #2 Axel Fox     May 2003 6016 Posts 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.
 2003-05-28, 15:40 #3 jocelynl   Sep 2002 2·131 Posts 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.
2003-05-28, 18:52   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
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. :)

 2003-05-28, 18:55 #5 Axel Fox     May 2003 25·3 Posts 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.
2003-05-29, 02:33   #6
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

2×7×521 Posts

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!

 2003-05-29, 07:47 #7 1260   Feb 2003 25 Posts 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?
2003-05-29, 12:28   #8

"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts

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.

 2003-06-07, 21:30 #9 clowns789     Jun 2003 The Computer 22·97 Posts Perhaps you can have something similar to Prime95 that guesses that stuff up.
 2003-09-29, 14:04 #10 only_human     "Gang aft agley" Sep 2002 2·1,877 Posts 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
 2003-09-29, 14:57 #11 only_human     "Gang aft agley" Sep 2002 1110101010102 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 13 2016-08-02 00:05 arbiter21 Information & Answers 17 2016-02-05 05:04 lidocorc Software 2 2008-11-08 09:26 bearnol Math 35 2005-10-12 14:33 clowns789 Miscellaneous Math 3 2004-05-27 23:39

All times are UTC. The time now is 21:36.

Sat Jan 16 21:36:41 UTC 2021 up 44 days, 17:47, 0 users, load averages: 1.70, 1.44, 1.34