mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-12-07, 02:18   #12
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3×167 Posts
Default

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.
JuanTutors is offline   Reply With Quote
Old 2005-12-07, 11:31   #13
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-07, 11:34   #14
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default 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.
Peter Nelson is offline   Reply With Quote
Old 2005-12-07, 11:59   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-07, 12:15   #16
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-12-07, 13:19   #17
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×457 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2005-12-07, 13:51   #18
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16228 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2005-12-07, 14:44   #19
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

2308 Posts
Default

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?
Dougy is offline   Reply With Quote
Old 2005-12-07, 15:01   #20
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-12-07, 18:27   #21
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

10218 Posts
Default

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
Peter Nelson is offline   Reply With Quote
Old 2005-12-07, 18:56   #22
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

3×5×89 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIGSEGV in xi3eK8 running torture test GordonWade Information & Answers 10 2018-02-18 00:07
Can I just start Prime95 by running torture test? marks9GIMPS Information & Answers 5 2011-06-05 18:44
Dual Core and running the same test..? Unregistered Information & Answers 1 2008-03-01 15:02
Prime95 crashing while running blend test day61 Hardware 1 2007-01-30 12:03
Running a LL test on 2 different machines lycorn Software 10 2003-01-13 19:34

All times are UTC. The time now is 15:47.

Thu Nov 26 15:47:52 UTC 2020 up 77 days, 12:58, 4 users, load averages: 2.07, 1.67, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.