20051206, 19:34  #1 
Oct 2005
36_{10} Posts 
Running LL test from both ends of the sequence?
I am not a mathematician. I have not studied how the LL method works, nor do not understand it.
A frequent question in these forums concerns the use of two (or more) processors to tackle the same candidate simultaneously in order to reduce the total procedure time. The answers are always that it is either minimally useful or cannot be done. (Now I am going to show my ignorance.) Would it possible set the LL test running twice on the same prime candidate starting at each end, as it were, and meeting somewhere in the middle? 
20051206, 19:43  #2  
Nov 2005
60_{8} Posts 
Quote:
John 

20051206, 19:44  #3  
Nov 2003
2^{2}×5×373 Posts 
Quote:
middle"? Explain how you think one would or could "start at each end"? And if your answer is "I'm not sure what I mean", then my answer is that one should never ask a question that one does not understand. Which is what I suspect that you are doing. One does not need to be a mathematician to apply a little common sense. I suggest that you do so. We have an initial starting value: L_0 = 4. We are trying to compute a final value: L_n. How do you propose we "start at each end" if we don't even know what the ending value is??? And it certainly is possible to do FFT's in parallel with little loss in efficiency. However, we can do Mersenne prime testing with ZERO loss in efficiency simply by giving separate exponents to separate machines. This is what is done now. 

20051206, 20:19  #4 
Oct 2005
2^{2}×3^{2} Posts 
Thank you, John. Exactly what I was hoping for: A concise reply. While I have no appreciation of its significance (nor do I need to), I understand the explanation.
RD  I made it perfectly clear that I do not understand how the LL test works and that I was demonstrating my ignorance. Regarding "starting at each end ... and meeting somewhere in the middle", I know exactly what I mean and so would you if you would "apply a little common sense." Just for your benefit, RD, if I wanted to test 1234567 for primality I could, for example, use a simple arithmetic test to discover if any integer between 2 and SQRT(1234567) was an exact divisor of 1234567. If I chose to I could increase the speed of my test by running it twice, one test starting at 2 and working upwards, the other starting at SQRT(1234567) and working downwards. "somewhere in the middle" the two would converge. Now I am NOT suggesting that the LL test works like this. In fact I was at pains to make clear that I have no understanding of how it works. "We have an initial starting value: L_0 = 4. We are trying to compute a final value: L_n. How do you propose we "start at each end" if we don't even know what the ending value is???" means nothing to me. "FFT" has no meaning to me beyond the words the letters represent. Congratulations, RD, for once again pointlessly attacking a selfconfessed "Ignorant GIMPSer". 
20051206, 20:58  #5  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Let me quote about the LL test from www.mersenne.org/math.htm
Quote:
Last fiddled with by smh on 20051206 at 21:02 

20051206, 21:05  #6  
Oct 2005
2^{2}·3^{2} Posts 
Quote:
Last fiddled with by MS63 on 20051206 at 21:08 

20051206, 21:06  #7 
∂^{2}ω=0
Sep 2002
República de California
3·7·19·29 Posts 
Actually, Bob's reply, though perhaps a bit more pointed than necessary, makes perfect sense to anyone who understands the basics of a oneway iterative procedure like the LL test. (I say "one way" because although it is theoretically possible to run it in reverse, that requires both modular square root taking, which is much harder than the modular squaring we use to proceed in the forward direction, and knowledge of the final value, which is impossible to attain without having first run the test in the forward direction.) Your example of trialdivision to test for factors is in no way analogous  in trialdividing to find a factor of N, you can easily calculate floor(sqrt(N)) and work backwards from that, if you like. Better still, you can precompute batches (or ranges) of trial divisors and assign each to a separate processor  the problem is trivially parallelizable. Generalize "meeting in the middle" to "testing all primes <= floor(sqrt(N))" and there you go.
In the LL test, we start with some appropriate initial value (e.g. 4), then do a bunch of squareandsubtracttwo steps. So far, no problem. But even if we could somehow run the test in reverse (add two, take square root) as fast as forward, what does "meeting in the middle mean" if we don't know the ending value from which we are supposed to run the "upper half" test in reverse? That's why your query is illposed. Oh, and in response to your other point, "FFT" stands for "Fast Fourier Transform"  it's the algorithm we use to efficiently effect the largeinteger multiplies needed for bignumber primality testing. Last fiddled with by ewmayer on 20051206 at 21:09 
20051206, 21:15  #8  
Oct 2005
100100_{2} Posts 
Quote:
As I said, I know the words that "FFT" stand for, but nothing beyond that. 

20051206, 22:05  #9  
Nov 2003
2^{2}×5×373 Posts 
Quote:
that total. And my response about starting and ending values was quite clear. You propose to start at "the end". But "the end" is the OBJECTIVE OF THE COMPUTATION AND IS UNKNOWN AT THE BEGINNING. This should be clear even without knowledge of how the algorithm works. Clear that is to anyone with two working brain cells. You failed to do even minimal reading of the subject material. Nothing is quite so irritating to a teacher as a student who asks questions without having done required homework and preparation. Maybe when you grow up you will understand this. 

20051206, 22:14  #10  
Nov 2003
1110100100100_{2} Posts 
Quote:
This explanation is quite elementary and quite clear. It is not just that you are ignorant of the algorithm, you seem unable to read even a simple description of it. Go away until you earn some basic mathematics and some basics of computer algorithms. And before you get upset, this is how any teacher handles a student who lacks the prerequisites to study a subject. 

20051206, 22:17  #11 
Aug 2002
Buenos Aires, Argentina
53A_{16} Posts 
The following is my interpretation of the original poster requirements.
Suppose that we want to run the algorithm in reverse, starting with S_{p2} = 0 (supposing that the number is prime) and we know how to perform the modular square root at the same speed as multiplication (of course, if you know such a method, please let me know). So the original poster wants to start computing S_{0} = 4, S_{1}, S_{2}, etc. and at the same time S_{p2} = 0, S_{p3}, etc. up to S_{(p3)/2}. Then we check whether both numbers are equal and if they are, the Mersenne number in question is prime. I think there is a big problem here. What of the two square root do we have to compute in the reverse computation? It appears that there are two possible values of S_{p3}, four values for S_{p4}, eight values for S_{p5}, etc. How do we know which is the correct one? 
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 