20051207, 02:18  #12  
Mar 2004
3×167 Posts 
Quote:
Quote:


20051207, 11:31  #13  
Nov 2003
2^{6}×113 Posts 
Quote:
not start "from the end" unless one knows what the "ending value" is. 

20051207, 11:34  #14  
Oct 2004
23^{2} Posts 
TRY to see through the mud
Quote:
However, one could criticise the lack of math formatting in it (the forum now supports nice symbols with effort). for example where is says 2P1, the P should be superscript (above) or alternatively (2^P)1. A reader who was not familiar with the algorithm might reasonably assume this meant double P then subtract one, whereas in fact the intended is raise 2 to the power P then subtract one. He could instead have been referred HERE: http://en.wikipedia.org/wiki/LucasLehmer_test However, the worked example of going through the sequence ought to have clarified that to someone bothered to THINK through what was posted. Where I DISAGREE with Bob is in saying that the PROPOSAL was unclear (to the originator and readers) and illposed. It was not posed FORMALLY but the idea was reasonable. What he is suggesting is that if there are a certain number of iterations in each LL test, could these be shared between two threads or processors working independantly. His ideas was that one thread perform the first half of the iterations, and the other perform the remainder of the iterations during the time the first thread is operating. By "meet in the middle" he means the two groups of iterations will finish about the same time "meeting" so that the iterations follow on from each other making the complete sequence. Most readers I think would figure this out. He was quite humble and was NOT of the "I've invented a new method" type poster. For someone with his stated (lack) of knowledge, the question posed is reasonable although would benefit from READING a little before asking. Where he goes astray is not to take advantage of the answers offered by those with more knowledge. As we have now pointed out, the proposal is impractical, and if we did know the endpoint (to work back from assuming that were even possible) the test itself would be redundant. I think it was sufficient to simply state that the proposed method was impractical because the result of one iteration depends on the previous and they need to be completed sequentially not in parallel. There is no need to flame on the basis of the original question. It did get me thinking for a moment whether some brilliant mathematician might be able for example to create some formula to shortcut to (say) the millionth iteration skipping the requirement to go through each but think that would have been explored as a dead end long ago, and such breakthrough would make the LL test obsolete. As we are still LL testing, it is obvious that such a breakthough has not been made yet (and quite possibly never will be). Possibly this would have been better asked in the "information and answers" thread, but perhaps the poster (foolishly? reasonably?) assumed that an area called "Math" could be ANY level of Math. I don't think this is a "crank" thread but might now be relegated to the "Misc Math" area. 

20051207, 11:59  #15  
Nov 2003
2^{6}×113 Posts 
Quote:
specific subject, knows the rudiments of computer algorithms. If not, they lack the prerequisites to even ask questions and should go elsewhere. Basic knowledge of algorithms would immediate show that one can not, in general. separate an iterative algorithm into two halves because the results of one half DEPEND UPON the results of the other. This has nothing to do with LL. If x_{n+1} = f(x_n) one can not compute x_{n+1} until x_n has been computed FIRST. And even if an inverse function exists [It does not in this case], one can not compute x_n = f^1(x_{n+1}) without knowing x_n!! One can't run backwards without knowing the ending value. But if we KNEW the ending value, we would not need to do the computation at all!!! If the original poster has no understanding of an iterative process, then he should not even be asking such questions. He lacks the prerequisites to understand any answer that might be given. 

20051207, 12:15  #16 
"Nancy"
Aug 2002
Alexandria
2^{5}·7·11 Posts 
He could assume that Mp is prime and must leave a zero residue, start the reverse compuatation from there and prove Mp composite by contradiction (when the residues in the middle don't match). That we don't know the correct final residue is not a problem here (except for the double checking effort). I doubt a meetinthemiddle match would suffice to prove primality, so we'd still need a proper sequential LL test in case of a match.
Of course, all this is foiled by the fact that taking modular square roots is 1. expensive and 2. not a singlevalued function. The forward test is just a path, the reverse test is a binary tree with number of nodes exponential in the depth. I added a small page to the FAQ of mersennewiki. Additions cordially welcome! Alex Last fiddled with by akruppa on 20051207 at 12:17 
20051207, 13:19  #17  
Feb 2004
France
2×457 Posts 
Welcome to the forum
Quote:
If you can stand the hard and acid (but often interesting) comments of Mister R.D. Silverman, then you can learn a lot here. You could also read Ribenboim's book. Tony 

20051207, 13:51  #18  
Feb 2004
France
1622_{8} Posts 
Quote:
Let take q=5 and Mq=31. We have: So, starting from the end, 0 has 2 roots (8 and 23), then 8 and 23 have 4 roots (14, 17, 5, 26) and 14 and 17 have 4 roots (4, 27, 9, 22). Look at: LLT DiGraph for details and proofs. Tony 

20051207, 14:44  #19  
Aug 2004
Melbourne, Australia
230_{8} Posts 
The 'meet in the middle' approach would determine the primality status of a Mersenne number with odd prime exponent.
Suppose we're testing for some odd prime , and we've assumed that and backcalculated the tree of possible moduli up to some point . If we then calculate in the usual manner and it turns out to be on the tree, it will prove the primality of since we would have the values of for already somewhere in the tree. Also if we calculated and it was not one of the possible moduli, then is composite, since it would be impossible to pass the Lucas Lehmer test. Of course this can only increase the amount of work necessary to determine the primality of this number. MS63: Quote:


20051207, 15:01  #20  
"Nancy"
Aug 2002
Alexandria
2^{5}·7·11 Posts 
Quote:
Quote:
Alex 

20051207, 18:27  #21 
Oct 2004
1021_{8} Posts 
Not all iterative functions need to exhibit the property of not being able to work backwards as a proof:
For example for simplicity let's say I want to do SEVEN iterations add 2 to n, and a certain test is true if the answer after the final iteration is 14. starting value zero After the First iteration: n=0+2 = 2 Second: n=2+2=4 Third: n=4+2 Fourth n=6+2=8 Fifth n=8+2=10 Sixth n=10+2=12 Seventh (and final) n=12+2=14 That's the SERIAL way. To do that in parallel, get processor one to perform iterations 1,2,3,4 and get the other processor to do the others backwards ie 7,6,5,4 So proc 1 gets 2,4,6,8 Proc 2 starts by assuming the final value 14 as the result of the 7th iteration It works back to say sixth value = 142=12 fifth value = 122=10 fourth value = 102=8 Since the middle (fourth) value is the same result when working through each half of the sequence, it is shown that the final value in the whole series was indeed 14. THIS IS A VERY SILLY EXAMPLE, as successive additions would usually be done with multiplication. However MS63 did not know that LL testing has properties that mean it can't work that way practically. As Bob pointed out though, when LL testing, the values in the sequence are not important to us, the final result is, and since that is what we are trying to find, we can't use it as one of our starting points, and working backwards is MUCH more computational effort than forwards in this case. The LL test uses enough computation already without making life harder for ourselves! The practical way to bring a speed up is to do EACH selfcontained iteration faster. Each processor takes PART of the calculation and the results are combined. Last fiddled with by Peter Nelson on 20051207 at 18:30 
20051207, 18:56  #22  
Aug 2002
Buenos Aires, Argentina
3×5×89 Posts 
Quote:
Quote:
Anyway this has no practical value because of the information I written in my last post. From there you would find that even for Mersenne primes the computed values of S_{(p3)/2} would be different. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SIGSEGV in xi3eK8 running torture test  GordonWade  Information & Answers  10  20180218 00:07 
Can I just start Prime95 by running torture test?  marks9GIMPS  Information & Answers  5  20110605 18:44 
Dual Core and running the same test..?  Unregistered  Information & Answers  1  20080301 15:02 
Prime95 crashing while running blend test  day61  Hardware  1  20070130 12:03 
Running a LL test on 2 different machines  lycorn  Software  10  20030113 19:34 