20030528, 06:13  #1 
Feb 2003
2^{5} 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(n1) mod M(n).
Suppose, if the unMODed value of S(n1) 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(n1) can be extremely large in comparison to M(n), but does using more hard disk space compensate for the time spent in recomputing from S(1)? 
20030528, 07:23  #2 
May 2003
2^{5}×3 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. 
20030528, 15:40  #3 
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^M1.
And theses are computed much faster than retreiving it from a disk. Joss. 
20030528, 18:52  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Re: Faster way to do LLT?
Quote:
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^(k1)+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(severalmillion). 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. :) 

20030528, 18:55  #5 
May 2003
2^{5}·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. 
20030529, 02:33  #6  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{3}·3·5·67 Posts 
Quote:
Oops, someone beat me to the punch in pointing this out! 

20030529, 07:47  #7 
Feb 2003
2^{5} Posts 
Okay. If it is really THAT LARGE, isn't there a mathematical conversion to do something similar?
I mean, if S(n1) = A mod M(n) = B mod M(n+k), then computation can start from S(n1) to S(n1+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(n1) mod M(n) saved in the results.txt file? Which is it, the Res64 or the WY1? 
20030529, 12:28  #8  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
Quote:
The catch is that the mod M(n) has been performed on every S(i) value up to S(n1). That is, there have been a string of up to n2 divisions by M(n) performed in order to reach the S(n1) value. If we're going to reuse the S(n1) 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 recalculating all the S(i) mod M(n+k) up to S(n1), then continuing to S(n+k1). IOW, we'll have to recalculate all the S(i) in mod M(n+k) anyway. Quote:
Quote:


20030607, 21:30  #9 
Jun 2003
The Computer
2^{4}·5^{2} Posts 
Perhaps you can have something similar to Prime95 that guesses that stuff up.

20030929, 14:04  #10 
"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^51 and 2^71 followed by a sequence that attempts to combine some of the work. Testing 2^51, 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^51 is prime Testing 2^71, 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^71 is prime Testing both 2^51 and 2^71, the LL sequence is: S(0)=4 S(1)=4^2  2 mod (31*127) = 14 S(2)=14^22 mod (31*127) = 194 S(3)=194^22 mod (31*127) = 2201 at this step, 2201 mod 31=0 therefore 2^51 is prime continue the sequence using 2201 mod 127=42 S(4)=42^22 mod 127= 111 S(5)=111^22 mod 127=0 ; therefore 2^71 is prime 
20030929, 14:57  #11 
"Gang aft agley"
Sep 2002
2·1,877 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 20030929 at 14:59 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
faster than LL?  paulunderwood  Miscellaneous Math  13  20160802 00:05 
Is it faster to run 1 worker or many?  arbiter21  Information & Answers  17  20160205 05:04 
My CPU is getting faster and faster ;)  lidocorc  Software  2  20081108 09:26 
3PRP faster than LL for GIMPS?  bearnol  Math  35  20051012 14:33 
Faster than LL?  clowns789  Miscellaneous Math  3  20040527 23:39 