Slashdot Mirror
45th Known Mersenne Prime Found?
An anonymous reader writes "The Great Internet Mersenne Prime Search (GIMPS) has apparently discovered a new world-record prime number. A GIMPS client computer reported the number on August 23rd, and verification is currently under way. The verification could take up to two weeks to complete. The last Mersenne prime discovered was over 9.8 million digits long, strongly suggesting that the new value may break the 10 million digit barrier — qualifying for the EFF's $100,000 prize!"
To what use will this long, long prime be put?
Absolutely none whatsoever. That's the beauty of mathematics.
And you only get 6 digits in prize money? What a rip off. That is only one $digit per 1.67 million prime digits.
...he asks on slashdot.
The beauty is that it doesn't HAVE to be useful.
Agreed. People should be using their extreme CPU cycles for things that matter, like helping the SETI program or running Microsoft Vista.
And work backwards, that will find the largest much faster than starting at zero.
You shouldn't think like that. Just think about your question, seriously. Whatever we do is pointless and useless and everything will be destroyed eventually through the heat death of the universe.
That being said, all that is important is that you have fun doing whatever you do. Believe it or not, some people really dig maths. Also, it's one more thing the species knows.
But when it comes to primes in the 10 million digit range (I couldn't even guess how many bits you would require for a number that large)
About 33 million bits ( ln(10)/ln(2) = 3.3219 ) or 4MB.
...even!
I guess some of us have different standards on beauty...
"Physics is like sex. Sure, it may give some practical results, but that's not why we do it." - Richard Feynman
I'm guessing it's the same logic at work here.
That is kinda less interesting because it depends on the system used to represent the number (binary, decimal, etc.) rather than an intrinsic property of the number
That has to be one of the best penis pill ad spoofs I've ever read. Kudos on that classy rewrite.
My only question is where the reasonably attractive blond chick who blinks too damn much comes in.
Try not to take me more seriously than I take myself.
"previously unknown"?
Uh, no. You have a very clunky Sieve of Eratosthenes. Digital roots isn't even a thing.
Also: numerological techniques would pertain to the spirituality of numbers and their mystic powers. Numeric techniques is what real computational mathematicians use.
I saw this joke posted on slashdot like, less than a week ago,b ut it's so relevant to the discussion ... fuck it.
"An engineer, a physicist and a mathematician were all staying in a hotel, when each of their rooms individually caught fire. The engineer did some basic math, flooded the floor and said, "it is out." The physicist did more complicated math, used just precisely the amount of water needed to put out the fire and said, "It is out." the mathematician did a lot of complicated math, said, 'I HAVE SOLVED IT!' and went back to bed."
Non impediti ratione cogitationus.
Testing a single candidate Mersenne prime takes a month of straight computation on a single 2.4 GHz Pentium 4 (assuming a 10 million digit prime, which would be the minimum to win the prize). This assumes the use of only one core, but you'd need at least 100 cores to make it anything resembling "quick" (~7 hours), if you could even parallelize the procedure that much.
Never mind the fact that only about one in 150,000 exponents will yield a prime, meaning that on average, 150,000 months of computation is required for a single prime to emerge, and furthermore, finding giant Mersenne primes is easier than most other kind of primes. So, I don't think your computer will find these giant primes "pretty damn quick".
Pessimism aside, I think this is a pretty impressive achievement considering that GIMPS doesn't have nearly the power of larger efforts like Folding@Home (GIMPS has around 500 GFLOPS while F@H has around 3372 TFLOPS, or 3372000 GFLOPS).
Aaah yes, the xkcd that made me stop reading xkcd.
As a chemist, i felt a bit upset at the elitist attitude of the comic, and no I do not think that biology is 'merely' applied chemistry, and therefore somehow less 'pure'.
Cry me a river, impure professional.
That's ridiculous. Being useless is not what makes math beautiful. There are plenty of useless things that aren't beautiful.
A lot of them post here.
echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;
I for one am glad that the EFF isn't using my donations for this award, beautiful mathematics or not. When I donate my hard-earned money to the EFF, I expect them to use it for something worthwhile. From TFA:
Prize money comes from a special donation provided by an individual EFF supporter, earmarked specifically for this project. Prize money does NOT come from EFF membership dues, corporate or foundation grants, or other general EFF funds.
Ah, arrogance and stupidity, all in the same package. How efficient of you. -- Londo Mollari
"Physics is like sex. Sure, it may give some practical results, but that's not why we do it." - Richard Feynman
Which is why Richard Feynman is known as the father of quantum mechanics.
Very Wrong
Large prime numbers are used in cryptography because it gives you massive amounts of digits that are not divisible by any other number. There's types of crypto that use multiple large prime numbers to build the keys from. If you use one of these as your seeds it will take a long time to crack anything encrypted as the number is huge and has no smaller factors. At 10 million digits you're going to take a long time to "guess" what it is.
Another fun relationship is between Mersenne Primes and Perfect Numbers, numbers whose factors add up to themselves.
If 2^n-1 is prime, (2^n-1)(2^(n-1)) is perfect (and has a distinctive pattern of digits in binary, to boot...). The proof in this direction is easy. Proving that all even perfect numbers are of this form is a little harder, but doable.
The hard one is proving whether or not there are any odd perfect numbers, and, if so, what form they might take. Nobody has done this yet.
...laura
The weighted FFT algorithm used by GIMPS is called the Irrational Base Discrete Weighted Transform (IBDWT), and it was designed with Mersenne numbers in mind.
You're almost right about GPUs getting enough memory to start tackling this sort of problem, but the issue isn't memory, it's floating point precision.
The FFTs being done by GIMPS are fairly large, and the overall error introduced by the FFT operations is roughly proportional to the log of the size of the dataset. So as the numbers become larger and larger, less and less data can be stored within each of the floating-point values. Which leads to larger transforms, which leads to less data that can be stored, etc. It's a vicious circle.
In the case of a 10 million-digit prime, the worst-case scenario ends up with 1 bit of the original value per float, and a transform size of about 2 ** 25. The values themselves will take up about 128 megs of video memory.
(Side note: the most efficient FFT algorithms involve a "scratch" buffer that stores intermediate results-- so for a 128-meg data set, we would really need to have at least 256 megs of usable space on the video card.)
In this case, if we have floating-point values with only 23 bits of mantissa (as is the case with most graphics cards), we would have to be sure that no more than 22 bits of error could creep in over the course of the calculations. But given the size of the transforms, that's not very likely. In reality, we're likely to lose the results to rounding errors.
The only real way out of this problem is to use higher-precision numbers. Some graphics cards offer 64-bit floats, but they come with a huge performance hit. There are also some techniques for "emulating" higher precision on a graphics card, but they're pretty application-specific, and I don't know that they'd work for FFTs.
So, yeah-- the long and the short of it is that graphics cards just don't have the required precision for large-integer multiplication at the size GIMPS is doing. Smaller numbers are okay (in fact, I've written code that uses GPUs to accelerate large-integer multiplication-- there IS a speedup), but 10 million digits just isn't possible yet.
Hope that clears things up!
At 10 million digits you're going to take a long time to "guess" what it is.
If there is only one known prime number with 10 million digits, then I reckon I could guess this one quite quickly.
U1NCaVpYUWdlVzkxSUhkcGMyZ2dlVzkx SUdoaFpHNG5kQ0JpYjNSb1pYSmxaQT09
I'm sure that would be odd if you found it.
rewriting history since 2109
His point was that while a number like 193 has a prime number of digits in decimal, if you change it to binary (11000001) it is no longer a prime number of digits long. So no, it is not an inherent property of the number. Every prime number has a prime number of digits in some base.
We hope your rules and wisdom choke you / Now we are one in everlasting peace
Can you prove that?
Sure. Every prime p has two digits in base p. QED.
Quantum Physics has many fathers. Classical physics is a bit of a slut.
It's been a long time.