mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software > Mlucas

Reply
 
Thread Tools
Old 2007-03-06, 18:32   #1
DeadSpam
 
Mar 2007

3 Posts
Question A Followup question on Mlucas...

Thank you all for answering my first question...now I have another question about the LL test as run in MLucas...

Do the statistical odds actually increase for a positive result as the number of iterations passed increases?

I'm running a test right now and am 580,000 iterations in...so far, no rounding errors and am churning out 2000 iterations every 50 minutes +- 30 seconds.

It would seem to me that the odds would have to increase, but I don't remember enough statistics to compute HOW much...

Thanks in advance!

DeadSpam is offline   Reply With Quote
Old 2007-03-06, 18:46   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

No, it does not. Because of how the LL test works it must complete all iterations before it knows whether it's prime or not.
More reading on LL test:
http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers
http://mathworld.wolfram.com/Lucas-LehmerTest.html
Mini-Geek is offline   Reply With Quote
Old 2007-03-06, 18:56   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by DeadSpam View Post
Thank you all for answering my first question...now I have another question about the LL test as run in MLucas...

Do the statistical odds actually increase for a positive result as the number of iterations passed increases?
:

Allow me to ask:

To what statistical odds do you refer? The number being tested is either
prime or composite. There are no "odds".

If you refer to the a priori probability of a *randomly selected* value of
2^p-1 being prime, this has nothing to do with the LL test.

I also do not understand you reference to "number of iterations". How
could anyone think that the number of iterations is related to probability in
any way? I need to understand your thinking before I can help. What
probability do you think is related to the number of iterations?
R.D. Silverman is offline   Reply With Quote
Old 2007-03-06, 21:30   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

I think the question was meant as Mini-Geek interpreted it: it assumed that the LL test can somehow tell half-way through that the number being tested is composite and stop there. But that is not how it works, as Mini-Geek already pointed out.

Alex
akruppa is offline   Reply With Quote
Old 2007-03-06, 23:39   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Allow me to ask:

To what statistical odds do you refer? The number being tested is either
prime or composite. There are no "odds".

If you refer to the a priori probability of a *randomly selected* value of
2^p-1 being prime, this has nothing to do with the LL test.

I also do not understand you reference to "number of iterations". How
could anyone think that the number of iterations is related to probability in
any way? I need to understand your thinking before I can help. What
probability do you think is related to the number of iterations?
Here's my view of what he meant: "Is it like a factoring attempt to where the longer it's run without stopping itself because it found a factor, the higher chances it's prime?" Or "Is the % done saying how many possible factors it's eliminated?" Meaning that if it's 99% done, 99% of the possible factors have been eliminated as factors, so the chances of it being prime are high.
note to deadspam: Don't take what I'm saying here as what is correct, that's in my first post. What I'm trying to say here is what you said, but in another way so other people understand it.
Mini-Geek is offline   Reply With Quote
Old 2007-03-07, 01:13   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I also do not understand you reference to "number of iterations".
< snip >
I need to understand your thinking before I can help.
I think most novices can easily be, and usually are, misled by Prime95's use of "iteration" in its user interface to refer both to a single TF division step (constituting a complete test of whether a particular candidate is a factor of the Mersenne number) and to a single L-L iteration (which is only one step within a single modular computation of S(p-2)).

As we've repeatedly seen implied by novices' questions in this forum, an average novice will fairly easily understand that the TF process is a series of tests of multiple individual candidate divisors of a Mersenne number, especially because this obviously parallels the definition of a prime as a number not divisible by any number other than itself and 1. In contrast, the L-L test's ultimate dependence on a division (of S(p-2) by the Mersenne number) is not nearly so clear to a novice.

(I'm tempted to assign significance to the fact that the meaning of the division in L-L is opposite to that in TF -- in TF, a zero remainder signals compositeness, while in L-L a zero implies primeness -- but if one's understanding goes that far, one is unlikely to be fazed by the opposite phases. :)

Novices' questions I've seen repeatedly show that they are thinking that the L-L test is basically a series of tests of individual candidate divisors, as in TF but somehow only modestly different in the detail of its (L-L) supposed "individual tests". This assumed parallel leads directly to misunderstandings.

Last fiddled with by cheesehead on 2007-03-07 at 01:31
cheesehead is offline   Reply With Quote
Old 2007-03-07, 05:51   #7
DeadSpam
 
Mar 2007

3 Posts
Question Well, now I'm REALLY confused...

Ok...

I guess I don't understand just wnat an 'iteration" consists of in the L-L test I am running.

Right now, I am thru 608,000 "iterations", with each 2K outputting that Res64: <Big Hex Number Here>.

In these 600K + iteratons, just WHAT has the program accomplished?

(Yes, I am a 'novice' nut will be able to follow the math if someone explains it...
SLOWLY...lol

Ed
DeadSpam is offline   Reply With Quote
Old 2007-03-07, 09:08   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

The Lucas-Lehmer test is pretty much just a huge exponentiation (although in GF(p2), but that's beside the point atm). The Mersenne number is prime if and only if the result of the exponentiation is a particular value, a residue of 0 in case of the Lucas-Lehmer test. What each iteration does is process a bit of the exponentiation, so it keeps getting closer to the final result. Unfortunately, we cannot tell what the final result will be by the intermediate results during the exponentiation, so all we can do is wait for the exponenitation to finish and get the final answer then.

Alex

Last fiddled with by akruppa on 2007-03-07 at 09:17 Reason: typesetting
akruppa is offline   Reply With Quote
Old 2007-03-07, 18:48   #9
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default it's calculating just one number.

Quote:
Originally Posted by DeadSpam View Post
Ok...
I guess I don't understand just wnat an 'iteration" consists of in the L-L test I am running.
Right now, I am thru 608,000 "iterations", with each 2K outputting that Res64: <Big Hex Number Here>.
In these 600K + iteratons, just WHAT has the program accomplished?
(Yes, I am a 'novice' nut will be able to follow the math if someone explains it...
SLOWLY...lol
Ed
I'd say it like that : the "LL test for Mp=2^p-1" is nothing else than the computation of ONE SINGLE NUMBER, which we could call X(p), and which is the rest of the division of cosh(2^(p-2) log(2+sqrt(3))) by Mp. If this is zero, p is prime; otherwise not. Basically, that's all.

For several different reasons this number is called S[p-1].
And it is calculated by repeating p times the formula S[n+1]=S[n]²-2, starting with S[1]=4. Each of these steps is one of the famous iterations. (Here p = 32 ooo ooo, e.g.)
The RES_64 (which I have never seen printed...) is just some (binary) digits of the number S[n], as a kind of debugging information while the calculation goes on...

This sequence grows extremely fast, but fortunately it is sufficient to keep at each step only the rest modulo 2^p-1, i.e. (roughly said...) about ("only"(!)) the least 10^7 decimal digits.
There digits make up the 8MB file which P95 saves every 30 mins.
So, each iteration corresponds to calculating the square of this "small number" - 2 and taking again the rest mod Mp.

So in some sense, prior to the last step, the program has achieved "nothing" yet!
(Well, one could quite easily see already from the last value, S[p-2], if p is prime. [Namely, if S[p-2] = +/- 2^((p+1)/2) mod Mp.] But from the penultimate, S[p-2], it would be already quite hard, and this would only save 2 iteration in 32 million. OK, that's not the whole information [for non-prime p the last values usually are periodically repeated so one could detect such a "looping" already before, but it's quite impossible to implement.])
m_f_h is offline   Reply With Quote
Old 2007-03-07, 21:10   #10
rgiltrap
 
rgiltrap's Avatar
 
Apr 2006
Down Under

89 Posts
Default

Quote:
Originally Posted by DeadSpam View Post
Ok...

I guess I don't understand just what an 'iteration" consists of in the L-L test I am running.

Right now, I am thru 608,000 "iterations", with each 2K outputting that Res64: <Big Hex Number Here>.

In these 600K + iteratons, just WHAT has the program accomplished?

Ed
I think the easiest analogy is this.

Remember the game people do with flowers ... "She loves me... She loves me not"

LL tests are like that but with a REALLY BIG flower with LOTS of petals.

Each petal you remove is an iteration and the residual is binary (loves me or loves me not). For LL tests the same applies but the residual is a "Big Hex Number".

As you remove the petals (complete iterations) you get closer to knowing the answer, but not any closer to what the answer will be. The answer will not be revealed until the final iteration has occurred. Either she loves you (prime) or not (not a prime).

Of course, even if she does loves you, it is only a matter of time before she leaves you for someone with a bigger PRIME
rgiltrap is offline   Reply With Quote
Old 2007-03-07, 23:31   #11
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

Quote:
Originally Posted by rgiltrap View Post
I think the easiest analogy is this.

Remember the game people do with flowers ... "She loves me... She loves me not"

LL tests are like that but with a REALLY BIG flower with LOTS of petals.

Each petal you remove is an iteration and the residual is binary (loves me or loves me not). For LL tests the same applies but the residual is a "Big Hex Number".

As you remove the petals (complete iterations) you get closer to knowing the answer, but not any closer to what the answer will be. The answer will not be revealed until the final iteration has occurred. Either she loves you (prime) or not (not a prime).
That is an awesome analogy. We need more posters like you.
jasong is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mlucas on ubuntu Damian Mlucas 17 2017-11-13 18:12
MLucas on IBM Mainframe Lorenzo Mlucas 52 2016-03-13 08:45
Mlucas on HP-UX/PA-RISC setup question smoky Mlucas 14 2009-05-05 15:40
mlucas on sun delta_t Mlucas 14 2007-10-04 05:45
A quick question regarding iterations in Mlucas... DeadSpam Mlucas 4 2007-03-05 14:06

All times are UTC. The time now is 00:56.

Fri Nov 27 00:56:29 UTC 2020 up 77 days, 22:07, 3 users, load averages: 1.42, 1.42, 1.45

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.