Slashdot Mirror
47th Mersenne Prime Confirmed
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..."
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?
So, all primes greater than two are odd, but only one of them is Odd's!
My first program:
Hell Segmentation fault
The admins missed the prime for about a month
http://mersenneforum.org/showthread.php?t=11996
Apparently the email that was supposed to be sent wasn't when the prime was reported
The Singularity is closer than you think
Quant
Discovering a prime number that distant from the zero is like discovering a Pluto like planet in outer space. But instead of Hubble telescope you need a powerful mathematical one..
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
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/
"I Don't Have Enough Faith to be an Atheist"
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
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?
No sig for the moment.
My calculator doesn't show it, anyone have the value of the prime?
The historical reasons for caring about Mersenne Prime are twofold: First, Mersenne primes correspond to perfect numbers (numbers that are the sum of their positive less than the number. So for example, 6 has as proper divisors 1,2 and 3 and 1+2+3=6). The ancient Greeks were fascinated by perfect numbers but could not do much to understand them. Euclid showed that if one had a Mersenne prime one can construct an even perfect number. In particular, if 2^n-1 is prime then (2^n-1)*2^(n-1) is perfect. Almost 2000 years later, Euler showed that every even perfect number is of Euclid's form. Thus, investigating Mersenne primes tells us more about perfect numbers. The oldest unsolved problems in math are 1) are there any odd perfect numbers? and 2) are there infinitely many even perfect numbers? Thus, investigating Mersenne primes helps us get closer to solving one of the two oldest unsolved problems in mathematics.
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.
On that note, I asked Wolfram the other day the tree in a forest thing and I finally have an answer!
like phosphorescent desert buttons singing one familiar song
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.
I want a new quote. One that won't spill. One that don't cost too much. Or come in a pill.
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.
I want a new quote. One that won't spill. One that don't cost too much. Or come in a pill.
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
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).
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
... the Great Old Ones will return, all life on earth will be destroyed.
weinersmith
According to the The Hitchhiker's Guide to the Galaxy, "Odd Magnar Strindmo" was a fourth generation accounting prefect on the third major planet of the second solar system in the first minor galactic cluster directly to the "left" of the vicinity of Betelgeuse - a star that has recently gone supernova. After achieving a modicum of fame for discovering the 47th known Mersenne Prime, during extended holiday on the, mostly harmless, planet named Earth, Mr Strindmo retired to a life of semi-luxury where he preferred to be called "Steve".
It must have been something you assimilated. . . .
"they could test 8 numbers at once, but they cannot test one number 8 times as fast."
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 a semaphore to say "stop, thread XYZ found an integer factor", if you want to be pedantic it's not 8X as fast but rather close to 8X as fast. I suggest the reason most implementations use one candidate per core is because most searches look at more than one candidate and the semaphore test makes the alternative implementation slightly less efficent.
And did you exchange a walk on part in the war for a lead role in a cage? - Pink Floyd.
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 primitive operations that the primality tests uses. So they're using FFT based multiplication steps to do the squaring which obviously can be parallelised quite well..
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
"Instead the test being discussed performs a series of squares and modulo reductions."
:)
Thanks for showing an old dog a new trick.
And did you exchange a walk on part in the war for a lead role in a cage? - Pink Floyd.
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
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
I say the entire number was photoshopped.
It's disappointing that they're using a home-grown management software instead of BOINC like many of the other distributed computing projects. I, for one, would be much more likely to add to the effort if I didn't have to worry about another piece of software and how it shared resources with the Einstein and Rosetta I'm already running.
My life's goal is to get a score of +3!
The dashed form of the English name is available at assist those who might actually want to read all or part of the +324 Megabyte name. :-)
chongo (was here)
So a couple decided to name their child "Odd". During his entire childhood, and sometimes during his adult life, Odd wad ostracized and bullied for his weird name.
Odd quickly grew to hate his name. When he wrote his will, he asked that nothing be written upon his tombstone, so that he would not, even in death, be remembered by that loathed name of "Odd".
Odd grew old and died. His children followed his wishes and placed a blank stone slab above his grave.
To this day, when people walked past his grave and its blank tombstone, they would remark, "Huh? That's odd."