mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2008-09-08, 22:56   #1
stars10250
 
stars10250's Avatar
 
Jul 2008
San Francisco, CA

3·67 Posts
Default GIMPS emotions and random observations

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.
stars10250 is offline   Reply With Quote
Old 2008-09-08, 23:25   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

Quote:
Originally Posted by stars10250 View Post
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.
Mini-Geek is offline   Reply With Quote
Old 2008-09-09, 06:04   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by stars10250 View Post
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.

Quote:
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!

Last fiddled with by cheesehead on 2008-09-09 at 06:07
cheesehead is offline   Reply With Quote
Old 2008-09-09, 13:28   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AB16 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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.
Mini-Geek is offline   Reply With Quote
Old 2008-09-10, 04:28   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.

Quote:
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, 21061-1).

232582657-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 21061-1 all the way to its square root.

Quote:
(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

Quote:
each higher bit level doubles the time spent on that level
But most folks don't really comprehend what that means.

Quote:
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 231 times as long as TF to 68 bits.

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

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

What's 2430 * 240,000 years? Over 2410 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?

Last fiddled with by cheesehead on 2008-09-10 at 04:51
cheesehead is offline   Reply With Quote
Old 2008-09-10, 04:48   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·5·307 Posts
Default

Quote:
Originally Posted by cheesehead View Post
What's 2430 * 240,000 years? Over 2410 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 268 in 1 hour. My quick back of envelope calculation gives ~673 years to reach 2530.5. Not so long really, and the level of patience is much less than we first assumed.

Last fiddled with by retina on 2008-09-10 at 05:35
retina is online now   Reply With Quote
Old 2008-09-10, 05:01   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by retina View Post
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.)

Last fiddled with by cheesehead on 2008-09-10 at 05:07
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
GPU and Random P-1 jocelynl Factoring 1 2016-11-25 05:14
Random bit in a word Prime95 Programming 19 2012-10-06 09:34
Observations with MaxHighMemWorkers petrw1 PrimeNet 5 2011-04-20 15:56
About random number (random seed) in Msieve Greenk12 Factoring 1 2008-11-15 13:56

All times are UTC. The time now is 05:43.

Mon May 10 05:43:40 UTC 2021 up 32 days, 24 mins, 0 users, load averages: 2.34, 2.83, 3.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.