4848917
story
Comments: 89 +- Science: 47th Mersenne Prime Confirmed on Saturday June 13, @05:54PM
Posted
by
kdawson
on Saturday June 13, @05:54PM
from the that's-odd dept.
from the that's-odd dept.
background: url(//a.fsdn.com/sd/topics/topicmath.gif); width:51px; height:47px;
math
background: url(//a.fsdn.com/sd/topics/topicscience.gif); width:62px; height:75px;
science
radiot88 writes to let us know that he heard a confirmation of the discovery of the 47th known Mersenne Prime on NPR's Science Friday (audio here). The new prime, 2^42,643,801 - 1, is actually smaller than the one discovered previously. It was "found by Odd Magnar Strindmo from Melhus, Norway. This prime is the second largest known prime number, a 'mere' 141,125 digits smaller than the Mersenne prime found last August. Odd is an IT professional whose computers have been working with GIMPS since 1996 testing over 1,400 candidates. This calculation took 29 days on a 3.0 GHz Intel Core2 processor. The prime was independently verified June 12th by Tony Reix of Bull SAS in Grenoble, France..."
Related Stories
It's not the men in my life, but the life in my men that counts.
-- Mae West
All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.
Odd's prime (Score:5, Funny)
Re: (Score:2, Funny)
Re:Odd's prime (Score:5, Funny)
Parent
Re: (Score:2)
The fact that Odd and Even both are common norwegian names serves to make the joke a lot better (for us natives, that is).
The joys of untested code (Score:5, Interesting)
The admins missed the prime for about a month
http://mersenneforum.org/showthread.php?t=11996 [mersenneforum.org]
Apparently the email that was supposed to be sent wasn't when the prime was reported
Re: (Score:2)
The code has been tested, as this is not the first prime numbers this project finds (far from it in fact).
Apparently it hasn't been tested enough though ;)
"telescope" from Intel (Score:3, Interesting)
Hmm (Score:4, Informative)
I honestly forget why I'm supposed to care about Mersenne primes. Like, I read something about them awhile back, it was somewhat interesting... and then--yeah. So:
http://en.wikipedia.org/wiki/Mersenne_prime [wikipedia.org]
In mathematics, a Mersenne number is a positive integer that is one less than a power of two.
A Mersenne prime is a Mersenne number that is prime. As of June 2009[ref], only 47 Mersenne primes are known; the largest known prime number (243,112,609 1) is a Mersenne prime, and in modern times, the largest known prime has almost always been a Mersenne prime.[1] Like several previously-discovered Mersenne primes, it was discovered by a distributed computing project on the Internet, known as the Great Internet Mersenne Prime Search (GIMPS). It was the first known prime number with more than 10 million base-10 digits.
For those who can't even remember what a prime is, it's a number that can only be divided (evenly) by 1 and itself. Here's a list of the first primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
The Mersenne primes are the largest known primes.
Prime numbers have applications in electronic security and encryption breaking. I'm not sure what other purpose there is to knowing them, other than knowing them. The Mersenne in particular seem to be merely mathematical curiosities right now.
I was much more excited by the discovery that the the Fibonnacci sequence is contained within the 1/89 calculation.
http://www.geom.uiuc.edu/~rminer/1over89/ [uiuc.edu]
Mersenne Primes correspond to Perfect Numbers (Score:5, Informative)
Parent
Re: (Score:3, Insightful)
Well, they may be unsolved problems, but again, they look like they have no relevance to anything, no application, other than being unanswered questions. But, like so many things, knowledge is valuable for its own sake, and who knows what revolution may result from what is now just a mathematical curiosity. Stealth-flight technology was originally harvested from a little known paper on radar written by an obscure Russian scientist. Kind of ironic that we were the ones to develop it. What you're really talki
Re: (Score:3, Insightful)
Re: (Score:2)
Well, I hate to break it to you, but you won't find any odd perfect numbers by finding Mersenne primes. (2^n-1)*2^(n-1) is going to be even for all n > 1.
You missed that part where every even perfect number is of that form. It says nothing about what form odd perfect numbers take, if they exist at all.
Re: (Score:2, Interesting)
Can we have the value? (Score:2)
Re:Can we have the value? (Score:4, Interesting)
Parent
Re: (Score:2)
The image has an alt-text containing the same text as the image, so you can still copy and paste from the page source if you wish
Re:Can we have the value? (Score:4, Funny)
In base 2, it's 1111[42,643,792 more 1:s]1111.
In base 16 it's 0xffff[2,665,229 more f:s]ffff.
Parent
Wolfram says so in 1 sec. (Score:2)
Well I don't know why it took 29 days for the computer to tell him it was so, wolfram alpha told me it was prime in ~1 second. [wolframalpha.com]
On that note, I asked Wolfram the other day the tree in a forest thing and I finally have an answer! [wolframalpha.com]
Re: (Score:2)
Really? I don't see where it generates output.
Change the last digit of the power to a 0 and it quickly comes up with FALSE, but I never see a "TRUE" for the original question. Where is the answer?
Re: (Score:2)
Re: (Score:2)
Yes, I know that. :-)
What I'm saying is that is listed under "input". That indicates to me it was reformulating your English question into a proper mathematical statement. Nowhere do I see output.
Try it this way and you'll see what I'm looking for: http://www29.wolframalpha.com/input/?i=is+(2%5E42%2C643%2C800+-+1)+a+prime+number [wolframalpha.com]
The "input" statement is the same formulation, but there is now a "result" block which was missing from your query. That result states "False" as opposed to changing the element
Re: (Score:2)
Here is a result which says true:
http://www29.wolframalpha.com/input/?i=is+3+a+prime+number [wolframalpha.com]
I guess it knows (2^n-1) can only be a prime number if n is prime (that's a known theorem).
Re: (Score:2)
Thanks. That leads me to believe it didn't really do the original calculation, instead it just gave up quietly.
Of course, they could always "cheat". They could create a list of known Mersenne Primes and just check against that...
Re: (Score:2)
It probably has a bunch of quick checks that can tell it "definitely not prime", "definitely prime" or just give up if none of the heuristics applies.
One of the checks they could add is the one you mentioned (a list of the known ones).
Re: (Score:2)
Re: (Score:2)
Ah I see what you are saying now, and you are rbarreira is probably right, it has given up. I thought that the input region saying it was a member meant it was true... Oh well, I did think it was pretty impressive that it new so quick!
I meant "knew so quick".
Re: (Score:2)
it has given up
Maybe if you gave it a month or two it would get back to you eventually ;)
Re: (Score:2)
At least it tries to given an answer on the swallow question [wolframalpha.com].
According to The Guide ... (Score:2)
It was done with GIMPS (Score:2)
Re:Cool processor (Score:5, Informative)
Parent
Re:Cool processor (Score:5, Funny)
Parent
Why is this useful? (Score:3, Insightful)
The answer is not in the summary, nor in the first page of the FA...
Buried somewhere in the linked site is this FAQ:
http://primes.utm.edu/notes/faq/why.html [utm.edu]
However all the answers are a bit unsatisfactory, IMHO...
So, I ask the great Slashdot hive-mind... What are the practical applications of Mersenne Primes and why are people paying money to find them?
Re: (Score:2)
Re:Why is this useful? (Score:4, Insightful)
Modulus or Division by such numbers can be accomplished with a few fast operations (bitwise Shift/And, a comparison, and maybe a subtraction) instead of a single very slow one (an actual division.)
Parent
Re:Cool processor (Score:4, Informative)
They're crunching 13-million-digit numbers with a desktop processor? Do they realize that they can put eight quad-core xeons in a machine and finish the calculation in a single shift instead of waiting a month?
I don't know about you, but the last 13 or so mersenne primes have been found using prime95 as a conduit for a mass distributed effort. I'm not sure where you live, but in most other places people can't just go out and put 8 quad-core xeons in a home machine.
Parent
Re:Cool processor (Score:5, Funny)
I'm not sure where you live
He lives at home with his parents (or maybe in a dormitory room) and doesn't have a clue as to what it actually costs to run a home.
Parent
Re:Cool processor (Score:4, Interesting)
Do they realize that they can put eight quad-core xeons in a machine and finish the calculation in a single shift instead of waiting a month?
What makes you think they aren't?
And what makes you think this man would pony up the serious coin for such a beast just to find a prime number?
Parent
Re: (Score:2)
Re: (Score:3, Insightful)
You don't get the $100k by searching for one prime though. You've got to be the lucky one that does the month long calculation on the number that actually happens to be prime.
It's like the lottery. You can't make a profit at it unless you're lucky. Otherwise, some big company would come in, invest a few million in number crunching, and take home all the bounties.
Re:Cool processor (Score:5, Informative)
The system used for this is GIMPS, the Great Internet Mersenne Prime Search. The system uses a distributed computing system using unused computing power in personal computers to search for various candidate primes. Computers do one of two things: Either trying to factor candidate Mersenne numbers or running a Lucas-Lehmer test on candidates without any small prime factors (the Lucas-Lehmer test is a special primality test for Mersenne numbers that is very fast). They use modular arithmetic and a variant of the Fast Fourier Transform to handle the multiplications which might otherwise become too difficult. The procedure is naturally a problem that can be made into a parallel processing problem like this since there are so many different candidate numbers to look at.
The summary doesn't mention but it is worth noting that the Lucas-Lehmer test allows one to check the primality of Mersenne numbers (numbers of the form 2^p-1, p prime) much faster than you can test the primality of generic numbers (or almost any other specialized form). Thus, for most of the last hundred years the largest primes known have been Mersenne primes. Currently the largest known prime is a Mersenne prime and the next 4 largest are also Mersenne primes. The GIMPS website - http://mersenne.org/ [mersenne.org] has a lot more details of both the math and software and explains how you can join in to help the project.
Parent
Re:Cool processor (Score:4, Insightful)
Do you realize that that's less efficient than using those 32 cores to calculate 32 independent numbers?
Parent
Re:Cool processor - No, they can't (Score:4, Informative)
Do they realize that they can put eight quad-core xeons in a machine and finish the calculation in a single shift instead of waiting a month?
No, they can't. Each iteration of the software requires the results of the previous iteration. It cannot easily be made to run like you want on multiple cores. The best they could do on the processor you describe is run 8 separate copies of the application, each taking one month to run...they could test 8 numbers at once, but they cannot test one number 8 times as fast.
Parent
Re:Cool processor - No, they can't (Score:5, Informative)
Actually that's not exactly correct, each iteration is also parallelizable. Most of the work in an iteration is a FFT, which is parallelizable.
http://www.fftw.org/parallel/parallel-fftw.html [fftw.org]
It's less efficient to do this than using each core for one independent number, so it's only used if quick checking of a number is desired (for example, when double-checking a previously found prime number).
Parent
Re: (Score:2)
Just because most searches use one number per core does not mean testing a single candidate can't be done very efficiently over multiple cores. You only have to think about the process for finding a prime, ie: testing factors, test if the candidate is it divisable by two, three, five, ect. The test for each factor is independent, so you COULD test 8 factors simultaneously, no?
The only communication between threads is
Re: (Score:3, Informative)
If you were going to test for primality by sieving then you could take a process that is millions of times slower than the primality test used, and speed it up by a factor of 8.
Instead the test being discussed performs a series of squares and modulo reductions. Each operand is dependent on the previous result - the entire computation is one long dependency chain and so cannot be split onto multiple cores in the way that you describe.
Although having said that, it all flips around again if you look inside the
Re: (Score:2)
Thanks for showing an old dog a new trick.
Re: (Score:2)
The primality test for these Mersenne primes does not consist of sieving, that would be way too slow given the size of these numbers.
Instead, the Lucas-Lehmer test is used, a very simple iterative process which you can implement in a few lines of code in most programming languages. It's described here:
http://primes.utm.edu/mersenne/index.html#test [utm.edu]
Re:Cool processor - No, they can't - correction (Score:2)
My bad...I misread your processor description...I thought you said 8-core. My answer is still correct though, I just used the wrong number of copies. They can run one copy per core, and the copies cannot exchange information.
Re: (Score:3, Informative)
As one of the IT guys who maintain the lab that found the 43rd and 44th primes at University of Central Missouri (formerly CMSU), I can tell you its one number per core. Also, these are production machines in computer labs as well as classroom, faculty and staff systems that run the GIMPS software.
We are a public university, its not like we have extra $5k machines just sitting around crunching a number. BTW, the systems that found the 43rd and 44th prime numbers were base model Dell GX280s.