20190119, 20:41  #1 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·829 Posts 
Is there utility in implementing an LLTlike sequence for GIMPS?
Was looking at http://tony.reix.free.fr/Mersenne/index.html this morning, and saw his LLTlike primality test using S_{0}=5, S_{i+1} = 2 S_{i}^{2}1 mod Mp proven, from 2005. http://tony.reix.free.fr/Mersenne/Pr...nneNumbers.pdf
It appears to me to be slightly slower to calculate than the standard LLT, S_{0}=4, S_{i+1}=s_{i}^{2}2 Mod Mp. Decrement or double decrement are trivial, O(1), but the doubling in front seems to me to be O(n log n log log n) additional work (where n is the exponent) in an fft based implementation. A big multiword bit shift left by one. Smaller contribution to the run time constant in front, but of similar order. Perhaps it would be useful, as a quick verification method of a newfound Mersenne prime. Computing a different conclusive sequence on the fastest available software and hardware might be faster than using a different software and different hardware architecture combination. Consider the cases where a new Mersenne prime is found with the usual LL sequence, with prime95/mprime or CUDALucas, or a PRP is found with gpuOwL or prime95/mprime and determined prime with CUDALucas. Then what are the verification hardware and software candidates? Presumably Mlucas, and Glucas again, which can take a while. Perhaps Reix's sequence offers a faster verification alternative. Would it be worthwhile to also include this different sequence in the standard prime95 software, to immediately launch a verification run on a newfound prime on the lucky owner's own system? That check run would inherently have a head start over any verification run by another user. The different seed, and different sequence, may give different error behavior on the same hardware/OS/software combination, just as different offsets may affect error results. (It might be more palatable for the unlucky user that gets a false positive somehow, to have his own system break the news that it did not duplicate, than to wait days or perhaps weeks for someone else to complete a run and tell him. Such a self check if positive would not constitute sufficient proof of primality for GIMPS or EFF, but may constitute near proof of compositeness if negative.) Given the current and future exponents in the tens or hundreds of millions, error checking is increasingly important. Does the Jacobi check apply to this sequence? Does some other more effective check apply? Being a different sequence, it should hit the round off errors differently. Because of the factor of two, I'd expect it to require slightly different exponent cutoffs for the various fft lengths. If oriented to verification rather than first time runs, its fft limits could be set rather more conservatively than for the standard LL sequence. Maybe this ground has all been thoroughly covered and there's nothing new or sufficiently useful to GIMPS here. But I don't recall seeing this sequence discussed. Especially not in the context of the recently added Jacobi and Gerbicz error checks. (If I just missed it, a URL pointer in the right direction would be welcome.) If it's worthwhile, it would eventually have Primenet consequences; another work type to handle, and another possible form of discovery information leak to be addressed. Or the client could report the self check run locally only, I suppose. Last fiddled with by kriesel on 20190119 at 21:08 
20190119, 21:31  #2  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2564_{16} Posts 
Quote:
is equivalent to S_{0}=10, S_{i+1}=S_{i}^{2}2 Mod Mp ...you are just tracking halfvalues with the former of the latter. S_{0}=10 has no difference to the S_{0}=4, strategically. Of course it can be run, at all times, as is; there is a configuration setting for it. 

20190120, 16:11  #3  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7×829 Posts 
Quote:
It seems somewhat similar to me, to George's resort sometimes to computing (xr)(x+r)+r^{2} if x^{2} hits a bad patch; using different algebra to accomplish the same end while avoiding numerical evaluation issues that can turn up. For Reix, square, bit shift left with carries, decrement, is different algebra and code than for the usual LL, square, decrement by two, and the operands are different values for the same iteration generally. Quote:
Result of search by any of various keywords, and =, for configuration settings compatible with the above statement: prime95: readme.txt no whatsnew.txt no undoc.txt no GUI menus no prime.txt no gwnum.txt no mprime: same doc files as prime95 (there are some interesting controls for PRP, not relevant to LL) CUDALucas 2.06: cudalucas.ini no readme.txt no source code nothing obvious Glucas 2.9.0 doc no Mlucas readme, no source no, appears to exclude it. Mlucas source snippet: /* Always use 3 as the p1 and Fermattest seed, and 4 for the LLtest seed: */ if(MODULUS_TYPE == MODULUS_TYPE_MERSENNE && TEST_TYPE == TEST_TYPE_PRIMALITY) iseed = 4; else iseed = 3; gpuowl not applicable (PRP) Being standardized on one seed value makes interim residues comparable. That's useful for comparisons between runs for where they begin to diverge in case of an error or more than one. Last fiddled with by kriesel on 20190120 at 16:12 

20190120, 18:32  #5  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}·2,393 Posts 
Quote:
Look: First method, in Russian usually called, 'методом тыка' (literally, 'prodding'  if you want to know if something is soft or hard, just prod it with a stick): Code:
$ gp q ? s=5;for(i=1,5,s=2*s*s1;print(2*s)) 98 9602 92198402 8500545331353602 72259270930397519221389558374402 ? s=10;for(i=1,5,s=s*s2;print(s)) 98 9602 92198402 8500545331353602 72259270930397519221389558374402 S=10; repeat { S := S*S2 } is equivalent to s*2=10; repeat { s*2 := s*2*s*22 } // now, divide by 2 > s=5; repeat { s := 2*s*s1 } ___________________ Next: Re: your PDF. and your words: "And it's not just half value, necessarily. A few simple examples evaluated numerically demonstrate that." Well, not if you don't know how to divide! You may want to learn that. Let's start with page 1. Mp=8191 Your table says (you even put mod Mp in the beginning of each line, so you have to live by the mod Mp rules. Floating division in this context is quite silly.) row 4: mod Mp (sic!) 1411 / 4801 = No it's not! mod Mp : 1411 / 4801 = 2 exactly and of course it will be 2 for every row, e.g. row 8: mod Mp 2113 / 5152 = 

20190120, 19:07  #6  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9572_{10} Posts 
Quote:
The doublechecker's computer also needs to be set to S_{0} = 10, then with different shifts, these two results would form a valid data pair, in the context of the project (and the S_{0} = 4, 10 or 2/3 should be recorded to the database). If the GIMPS server was interested in a randomized control trial of this kind, it could be sending some tasks with the seed of 10, but twice. By the way, quick, easy homework for all interested: calculate S_{0} = 2/3 (Mod 2^{p}1) without searching the forum. Just take a sheet of paper and find out what it is. It is an "integer" modular value. 

20190120, 20:49  #7  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·829 Posts 
Quote:
Re row 4 and 8: I'm looking at the actual magnitudes that need to be represented and processed by the algorithm. Perhaps it would have been better if I'd more fully expressed the rows as "Value after the mod Mp operation" instead of merely "mod Mp" but that takes up a lot of space. Or "remainder". You seem to be saying 1411(plus an imputed 8191) / 4801 = 2. That's true. (It seems a bit arbitrary to choose adding a single Mp when it's convenient to your point; magnitude ratios go all over the place for differing multiples of Mp added back, and there's practically speaking a disincentive to add back anything in performing the actual calculations.) And that seems to me irrelevant to the problem at hand, of ensuring correct execution; the values that must be represented and used for the next iteration and handled without error are not padded with multiples of Mp that have already been removed, at the mod Mp operation. The point of the ratio was to show that the relative magnitudes that must be handled per iteration fluctuate differently and do not between the two series have values always corresponding to a 2:1 ratio in magnitude. That seems to me a source for possibly different error behavior to occur. The algorithm does not have to be capable of squaring 9602 errorfree, if the modulo reduction was complete. Now, to look at that more closely, I'd need to break the residues into parts for a multiword representation, but that is more than I'm inclined to do right now. Perhaps you'd be happier if I had used deltas rather than ratios. I used ratios of the actual values because you earlier made reference to a constant ratio. Which does not hold in all iterations. Equivalence is not equality. 1411 is a SMALLER magnitude than 4801 to represent in storage and process in the next iteration and survive the roundoff error and other errors. Its magnitude is not larger by a factor of two than 4801. A separate matter is your impolite tone. George and Ernst are worth emulating in that respect. I don't understand why you seem hostile to someone trying to understand better. And who are you that you believe you can dictate the terms of discussion? Maybe it's a language thing, or a bad day, I don't know. Last fiddled with by kriesel on 20190120 at 20:51 

20190120, 21:21  #8  
Einyen
Dec 2003
Denmark
2·7·227 Posts 
Quote:
3^{1} = 2*(2^{p}+1)/31 = 2*W_{p}  1 (Mod 2^{p}1) S_{0} = 2/3 = 2*3^{1} = 2*(2*W_{p}  1) = 4*W_{p}  2 = 2^{p}+1 + W_{p}  2 = W_{p} (Mod M_{p}) Spoiler tag does not work with SUP and SUB tags for some reason. Last fiddled with by ATH on 20190120 at 21:59 

20190120, 22:48  #9  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22544_{8} Posts 
Noch eine Minute, bitte.
Quote:
Maybe you quoted from him correctly, maybe you didn't. You asked if S0=5, Si+1 = 2 Si^21 mod Mp was a new method, and you received an answer. Quote:
Working mod Mp means you operate on mods: Mod(1411,8191) / Mod(4801,8191) = 2 exactly The exact way you can visualize it?  there are many shortcuts, including what you wrote (with one important change: No, not "when it's convenient to your point". When numerator is odd. That's all. ... Mod an odd number, a half always exists and this how it can be visualized: if numerator is even, divide by 2; else add modulo and divide by 2) Quote:
A suggestion to learn about modular division was impolite? Ok, it was curt. It certainly wasn't hostile and was not out of place while discussing the modular algorithm that you suggested. It helps you get to the answer and get to many more answers. While, in contrast, by refusing to do so you will continue to run in darkness in circles and lose time. Which is fine if that's what you want  nobody is forcing you. It was just a suggestion, and it was polite: "You may want to learn that". "I'm here to help  if my help's not appreciated then lotsa luck, gentlemen." (W.Wolf) 

20190120, 23:03  #10 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}×2,393 Posts 

20190121, 17:44  #11  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
7·829 Posts 
Quote:
I provided a link to his paper in the beginning of post one, for the convenience of any reader. Here it is again, and, with red boxes added by me to highlight the most relevant initial portions, on the screen capture attached. http://tony.reix.free.fr/Mersenne/Pr...nneNumbers.pdf Actually following what Reix wrote occurred to me as different computer code: LL: square and subtract two mod MP LLReix: square and double and subtract one mod MP And there's precedent for using nonoptimalcomputetime code sequences as workarounds for numerical issues that arise at times. Quote:
Quote:
A part of the possible point of the Reix series is the numerical differences in interim computation values. Another part is the different iteration formula. Quote:
Quote:
The conclusion that base is already well covered is not surprising. Quote:
There's more, but (because I couldn't find the "beating a dead horse" smily I've seen here before) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Implementing Factoring Algorithms  Raman  Hobbies  45  20090511 05:11 
Implementing Chinese Remainder Theorem in C  ShiningArcanine  Software  3  20071117 05:55 
Implementing MPQS: SOS!  smoking81  Factoring  10  20071002 12:30 
Implementing algorithms, did I do this right?  ShiningArcanine  Programming  18  20051229 21:47 
Prime Shuffle Utility  HiddenWarrior  Programming  6  20041104 05:21 