mersenneforum.org > Math Running LL test from both ends of the sequence?
 Register FAQ Search Today's Posts Mark Forums Read

2005-12-07, 02:18   #12
JuanTutors

Mar 2004

499 Posts

Quote:
 Originally Posted by R.D. Silverman (1) Your question is not well posed. What do you mean by "meeting in the 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.
Mr. Silverman: I don't think you are so mathematically gifted that you are unable to read the question posed and understand what it means. The question is actually asked very clearly and coherently. If you don't want to answer the question in the same language, don't respond.

Quote:
 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.
Start at 0 and work backwards until you get half way. At first site it looks like it would be possible. People around here would know whether that is possible or not, so this is a great place to ask.

2005-12-07, 11:31   #13
R.D. Silverman

Nov 2003

723210 Posts

Quote:
 Originally Posted by dominicanpapi82 Mr. Silverman: I don't think you are so mathematically gifted that you are unable to read the question posed and understand what it means. Start at 0 and work backwards until you get half way. At first site it looks like it would be possible. People around here would know whether that is possible or not, so this is a great place to ask.
I understand very well what it means. It is nonsensical gibberish. One can
not start "from the end" unless one knows what the "ending value" is.

2005-12-07, 11:34   #14
Peter Nelson

Oct 2004

232 Posts
TRY to see through the mud

Quote:
 Originally Posted by MS63 Clear as mud!
I agree with Bob, try to make SOME effort to understand this explanatory post because it was written to HELP you see the method and why your proposal is impractical. Can you really not see ANYTHING in this "mud" ???

However, one could criticise the lack of math formatting in it (the forum now supports nice symbols with effort).

for example where is says 2P-1, 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/Lucas-Lehmer_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 ill-posed. 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 end-point (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.

2005-12-07, 11:59   #15
R.D. Silverman

Nov 2003

723210 Posts

Quote:
 Originally Posted by Peter Nelson Where I DISAGREE with Bob is in saying that the PROPOSAL was unclear (to the originator and readers) and ill-posed. 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.
I assume that anyone posting here, while not having knowledge of this
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 L-L. 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 pre-requisites to
understand any answer that might be given.

 2005-12-07, 12:15 #16 akruppa     "Nancy" Aug 2002 Alexandria 25·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 meet-in-the-middle 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 single-valued 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 2005-12-07 at 12:17
2005-12-07, 13:19   #17
T.Rex

Feb 2004
France

2·457 Posts
Welcome to the forum

Quote:
 Originally Posted by MS63 I am not a mathematician...
Welcome to the Math forum, MS63 !
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

2005-12-07, 13:51   #18
T.Rex

Feb 2004
France

2×457 Posts

Quote:
 Originally Posted by alpertron 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 Sp-3, four values for Sp-4, eight values for Sp-5, etc. How do we know which is the correct one ?
Good comment, Alpertron !
Let take q=5 and Mq=31. We have:

$\large 4^2-2 \equiv 14 \ , \ 27^2-2 \equiv 14 \ , \ 9^2-2 \equiv 17 \equiv -14 \ , \ 22^2-2 \equiv 17 \equiv -14$
$\large 14^2-2 \equiv 8 \ , \ 17^2-2 \equiv 8 \ , \ 5^2-2 \equiv 23 \equiv -8 \ , \ 26^2-2 \equiv 23 \equiv -8$
$\large 8^2-2 \equiv 0 \ , \ 23^2-2 \equiv 0$

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

2005-12-07, 14:44   #19
Dougy

Aug 2004
Melbourne, Australia

23·19 Posts

The 'meet in the middle' approach would determine the primality status of a Mersenne number with odd prime exponent.

Suppose we're testing $M_p$ for some odd prime $p$, and we've assumed that $s_{p-2} \equiv 0 \pmod {M_p}$ and back-calculated the tree of possible moduli up to some point $n$. If we then calculate $s_n$ in the usual manner and it turns out to be on the tree, it will prove the primality of $M_p$ since we would have the values of $s_m$ for $n \leq m \leq p-2$ already somewhere in the tree. Also if we calculated $s_n$ and it was not one of the possible moduli, then $M_p$ 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:
 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.
Surely your second testing process would take longer than your first. Firstly there's more bookkeeping, I.e. keeping track of what numbers have been used for trial divison, etc.. Secondly it's more likely to be divisible by a smaller number. Am I missing something?

2005-12-07, 15:01   #20
akruppa

"Nancy"
Aug 2002
Alexandria

25·7·11 Posts

Quote:
 Originally Posted by Dougy The 'meet in the middle' approach would determine the primality status of a Mersenne number with odd prime exponent.
Only if we assume that it is prime - otherwise we'll have a real hard time taking square roots. And a proof of primality that is based on assuming that the number is prime is... umm, well... questionable.

Quote:
 Originally Posted by Dougy Surely your second testing process would take longer than your first. Firstly there's more bookkeeping, I.e. keeping track of what numbers have been used for trial divison, etc.. Secondly it's more likely to be divisible by a smaller number. Am I missing something?
The problems are completely different. With trial division, you have a search space that can be neatly partitioned any way you want. Trivially parallelizable. The LL test is an iterative procedure - the result of each step is the input for the next. Not parallelizable.

Alex

 2005-12-07, 18:27 #21 Peter Nelson     Oct 2004 232 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 = 14-2=12 fifth value = 12-2=10 fourth value = 10-2=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 self-contained iteration faster. Each processor takes PART of the calculation and the results are combined. Last fiddled with by Peter Nelson on 2005-12-07 at 18:30
2005-12-07, 18:56   #22
alpertron

Aug 2002
Buenos Aires, Argentina

101001101012 Posts

Quote:
 Originally Posted by akruppa Only if we assume that it is prime - otherwise we'll have a real hard time taking square roots.
We can assume "a priori" that the number is prime. If we cannot compute the square root, the Mersenne number must be composite, because that means that there is no previous element of the sequence.
Quote:
 Originally Posted by akruppa And a proof of primality that is based on assuming that the number is prime is... umm, well... questionable.
If we start with Sp-2 = 0 and find that both computed values of S(p-3)/2 have the same value we can safely assume that the Mersenne number is prime because by computing the different LL steps we would rediscover S(p-3)/2 + 1, S(p-3)/2 + 2, ... whose values were found in the reverse computation.

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(p-3)/2 would be different.

 Similar Threads Thread Thread Starter Forum Replies Last Post GordonWade Information & Answers 10 2018-02-18 00:07 marks9GIMPS Information & Answers 5 2011-06-05 18:44 Unregistered Information & Answers 1 2008-03-01 15:02 day61 Hardware 1 2007-01-30 12:03 lycorn Software 10 2003-01-13 19:34

All times are UTC. The time now is 19:06.

Sat Oct 24 19:06:17 UTC 2020 up 44 days, 16:17, 0 users, load averages: 1.44, 1.58, 1.71