Forgot your password?
typodupeerror
Math

45th Known Mersenne Prime Found? 396

Posted by samzenpus
from the really-big-number dept.
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!"
This discussion has been archived. No new comments can be posted.

45th Known Mersenne Prime Found?

Comments Filter:
  • by Anonymous Coward on Wednesday August 27, 2008 @08:23PM (#24773073)

    And you only get 6 digits in prize money? What a rip off. That is only one $digit per 1.67 million prime digits.

    • Well now, as the summary points out, it could be less than 10 million digits. For instance, it could be the previous record holder plus one. My calculator only goes up to 8 digits, so I can't test it one way or another.

  • GPU's? (Score:5, Interesting)

    by EdIII (1114411) * on Wednesday August 27, 2008 @08:30PM (#24773171)

    Testing a single 10,000,000 digit number takes two months on a 2 GHz Pentium 4 computer

    According to their own benchmark pages a newer Core 2 Duo E8500 process in less than 21 days. Just recently I know that password cracking programs were written to use GPU's which dramatically increased the performance. Wouldn't writing code to run this on the GPU's result in even faster processing times?

    • Re: (Score:3, Informative)

      GPU performance is geared towards floating point and massively parallel operations on small numbers. Unfortunately, neither of those characteristics are particularly handy for dealing with large primes.

      Even in the general computing scenarios where they are useful, they are frequently wasting a lot of resources to accomplish the task. The Folding@Home team has noted that due to poor random access performance it is usually more efficient to recompute values than to retrieve them from memory. In practice, t

      • Re:GPU's? (Score:5, Interesting)

        by fredrikj (629833) on Wednesday August 27, 2008 @09:09PM (#24773579) Homepage

        The Lucas-Lehmer test for Mersenne primes consists of repeated multiplication (modulo a fixed large number). Large-integer multiplication is done via floating-point FFT, which is nothing but massive amounts of operations on small numbers. I don't know how FFT implementations for GPUs compare, but intuitively I think they ought to be at least as fast as for CPUs. The primes tested by GIMPS are small enough to fit entirely in GPU memory, so latency doesn't seem like a problem.

        (I don't really know much about any of this, so feel free to correct/enlighten me.)

        • Re:GPU's? (Score:5, Informative)

          by Anonymous Coward on Thursday August 28, 2008 @01:57AM (#24775571)

          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!

  • I was hoping it would be me. I have been using ./mprime on all my boxes for years now.

    Congrats to the team and world.

  • by Anonymous Coward on Wednesday August 27, 2008 @08:47PM (#24773341)

    And work backwards, that will find the largest much faster than starting at zero.

  • Prediction (Score:5, Funny)

    by mrroot (543673) on Wednesday August 27, 2008 @08:53PM (#24773415)
    Sure, you are excited now, but I predict you will look back on this moment with indifference once the 46th is discovered. For now, I'm going to keep the champagne on ice.
  • by The G (7787) on Wednesday August 27, 2008 @08:56PM (#24773429)

    ...even!

  • by Anonymous Coward

    ... why the EFF considers it worth $100,000 of donated funds to pay someone for finding a 10,000,000-digit prime number. That is not what my donations were intended to do.

    Go fix warrantless wiretapping, then go looking for prime numbers, kthxbye.

    • by John Miles (108215) on Wednesday August 27, 2008 @09:10PM (#24773585) Homepage Journal

      FTFA:

      (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.)

      Still, it's not hard to think of some more, well, "electronic frontier-ish" applications for that kind of money. The FPGA-based DES keysearch engine they built a few years back was cool. OTOH, this Mersenne prime business just sounds like they're paying for something that will become trivial soon enough anyway.

    • by Tacvek (948259)

      Umm, that prize money was from a single donation that was made fir the precise purpose of funding this search. They are not using any other donations for this purpose. (I'm betting it was a half million dollar donation (or perhaps a full million dollar donation) made with the condition that part of it be reserved for this purpose. But the remainder of the donation would still be too large for the EFF to ignore.

  • by Rob Kaper (5960) on Wednesday August 27, 2008 @09:08PM (#24773571) Homepage

    The submitter or editor could have at least typed the number into the summary. Lazy bastards.

  • by pig_man1899 (1143237) on Thursday August 28, 2008 @01:53AM (#24775557)
    Mathematician #1: How are we going to find the 46th Prime?
    Mathematician #2: Bring out the GIMPS.
    Mathematician #1: The GIMPS is sleeping.
    Mathematician #2: I guess you're going to have to wake him up then.

Programmers do it bit by bit.

Working...