GIMPS emotions and random observations

[stars10250]

Last night at 2 am my computer finished its (my) first two LL tests ever. I told myself I wouldn’t get up in the middle of the night to check it, but like clockwork I woke up at 1:50. The past month has been something of a roller coaster, from the new learning curve, to the worry over meltdown on really hot days, to the panic of two weather-related power outages, to the impending discovery of M45 and 46. I never imagined I would get so caught up in it. I’m disappointed my numbers weren’t prime, but I knew the odds weren’t good going in. So, presumably, like many of you, I think my new interest will be moving myself up the producers list (woo hoo). The cost of electricity is also starting to consume more of my thoughts, and I’m seeing the value of pulling the plug on two older systems and maybe replacing them with a nehalem system in the fall. I presume everyone goes through these phases....when does it end?

As for observations, I’m surprised the calculation doesn’t use much ram. At first I read a lot of comments like “feed it as much ram as you can,” so I built a 2Gb system. Short of the one stage where it will use a lot, it doesn’t ever use much over 50 Mb (and that’s for 2 instances). Then I read the readme file by George where it says all this and felt stupid :) Will the code stop if a factor is found? I suspect the algorithm does not work this way, because both my calculations made it to 100% before declaring my numbers weren’t prime. I guess I don’t understand this part.

[TimSorbet]

Originally Posted by stars10250

Will the code stop if a factor is found? I suspect the algorithm does not work this way, because both my calculations made it to 100% before declaring my numbers weren’t prime. I guess I don’t understand this part.

No, it doesn't know until it is at 100%.
See http://www.mersenne.org/math.htm under "Lucas-Lehmer testing" (the rest of that page is interesting reading for info on the rest of the tests GIMPS runs, but the LL test is the part that takes the longest that proves primality) and http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers for more info.

[cheesehead]

Originally Posted by stars10250

I presume everyone goes through these phases....when does it end?

Depends ... what is your position on the so-far-unsettled question of whether there are an infinite number of Mersenne primes? :)

Death cures addictions, if nothing else does beforehand.

Will the code stop if a factor is found?

Expanding on Mini-Geek's answer, but at the risk of confusing you --

There are four different types of testing in GIMPS software (Prime95/mprime): trial factoring, P-1 factoring, ECM factoring and the Lucas-Lehmer test. (However, your two assignments included only the L-L type.)

The answer to your question for each of those types is, respectively,

TF: yes, and could be at any stage (1% to 99 %).

P-1 & ECM (these are the only types that use lots and lots of RAM): yes, but it can find a factor only after 100% of a computation is completed.

L-L: it never actually finds a factor, but after 100% of a long computation is completed it can tell you definitely whether or not some factor exists.

For a GIMPS novice that may be confusing, because your assignments so far apparently included only the fourth type, L-L testing. That's the most time-consuming type, and we need the most help with it, so most active GIMPS assignments at any given time are of that type.

OTOH, L-L testing is the only type that can open the door to eternal mathematical fame, and a bit of mortal fortune, because it's the only type that can find a Mersenne prime!

[TimSorbet]

Originally Posted by cheesehead

OTOH, L-L testing is the only type that can open the door to eternal mathematical fame, and a bit of mortal fortune, because it's the only type that can find a Mersenne prime!

Unless you consider the possibility of trial factoring every possible factor, but that would take an EXTREMELY long amount of time (much, much longer than an LL test, but it can stop at any time if it finds a factor), as each higher bit level doubles the time spent on that level, and must go to about half the exponent (normally at GIMPS's current level it goes to about 68, to prove primality by TFing along would require about 21952114) to be completely proven.

[cheesehead]

Originally Posted by Mini-Geek

Unless you consider the possibility of trial factoring every possible factor,

I don't think it's a good idea to give novices the idea that it could _ever_ be practical to completely trial-factor any unfactored Mersenne number.

but that would take an EXTREMELY long amount of time

By failing to provide any numerical measure of what is meant here by "EXTREMELY long", you let the novice reader imagine that it is possible at all, perhaps after only a century of more hardware advances.

It isn't, for any Mersenne that is currently unfactored (say, 2¹⁰⁶¹-1).

2^32582657-1 (the 44th Mersenne prime) is, by most standards of everyday life, an "EXTREMELY large" number. But the time its L-L test took (6 days for the verification run) is nothing compared to the time needed to TF mere 2¹⁰⁶¹-1 all the way to its square root.

(much, much longer than an LL test,

HOW much longer?

By letting the novice imagine that you may mean only, say, a million times as long as an LL test, you fail to convey the limitations of the trial factoring method.

Here's a posting in which I presented the numerical impossibility of TFing a small Mersenne number all the way to its square root: http://mersenneforum.org/showpost.ph...10&postcount=9

each higher bit level doubles the time spent on that level

But most folks don't really comprehend what that means.

normally at GIMPS's current level it goes to about 68

Do you want the novice to imagine that going to, say, 99 bits is practical?

TF to 99 bits would take about 2³¹ times as long as TF to 68 bits.

Suppose TFing 2¹⁰⁶¹-1 to 68 bits took only, say, one hour (faster than current GIMPS computers can manage). Then TF to 99 bits would take 2³¹ hours. That's over 240,000 years.

But if this were being done on 2¹⁰⁶¹-1, TF to 99 bits would take us less than one 2^-430th of the way to the square root of 2¹⁰⁶¹-1.

What's 2⁴³⁰ * 240,000 years? Over 2⁴¹⁰ times the estimated age (13 billion years) of the known universe!

Now, how much longer than that would it take to do that TFing-to-the-square-root on a Mersenne with an exponent in the forty-millions than for one with an exponent of just 1061?

[retina]

Originally Posted by cheesehead

What's 2⁴³⁰ * 240,000 years? Over 2⁴¹⁰ times the estimated age of the known universe!

Aha, so you admit it is possible! We just need a little bit of patience.

But what if we consider Moores law? Assume the most optimistic prediction of computer transistors (and thus core count) doubling each 18 months. Take the figure of factoring up to 2⁶⁸ in 1 hour. My quick back of envelope calculation gives ~673 years to reach 2^530.5. Not so long really, and the level of patience is much less than we first assumed.

[cheesehead]

Originally Posted by retina

But what if we consider Moores law?

What if we consider the limits of Moore's law (which isn't a law like the laws of physics, anyway)? The doubling can't go on for more than another few tens of times, certainly not more than the maximum lifetime of any current GIMPS participant.

(Considering quantum mechanics, the Planck time and so forth, see http://mersennewiki.org/index.php/Lu...le_Explanation for some related numbers.)