| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
GIMPS clients
Contents
Theory and practice
The Great Internet Mersenne Prime Search (GIMPS) as a project is based on two related items: theory and practice.
The first part of the theory is that a special test called a Lucas-Lehmer test allows very large Mersenne prime candidates to be tested for primality ("is it a prime?") faster than other sorts of would-be primes of the same magnitude. "Faster" here is still measured in weeks, but that certainly beats years.
Another essential element of this is that while you can write a simple version of the Lucas-Lehmer test in half an hour using Java or any other language with "Big Integer" support, ordinary multiplications turn out to get very slow, very quickly even if you recode the traditional multi-word algorithms in assembler. Long before we get to where the GIMPS project is testing candidates, such programs, while correct, simply take too long to get an answer.
So, another theory part is based on some very clever tricks involving "how fast can we multiply." For obscure reasons (see Knuth, "Semi-numerical algorithms" among others), it turns out that a convolution version of a Fast Fourier transform is the only way to multiply really huge numbers in a time that any human being would want to wait for. That is, once numbers get really big, it is worthwhile to set up the multiplication using FFTs and (counter-intuitively to the beginner) using floating point.
The "practice" part is that George Woltman has honed a very highly tuned version of this FFT multiply process in assembler that even runs different bits of code for AMD versus P III versus P IV Intel.
So, to test a number efficiently, one must apply the theory to get the tests down to the "weeks" range. The assembler cuts the time by at least another factor of two over straight C.
Current best software
Mersenne prime-hunting software with highest throughput by hardware type (as of June 2018):
| Hardware | GIMPS assignment type | ||||
|---|---|---|---|---|---|
| LL test | PRP test | Trial factoring | ECM factoring | P-1 factoring | |
| Intel-compatible CPU (x86 / x64) | Prime95 / Mprime | ||||
| Nvidia GPU | CUDALucas | N/A | Mfaktc | N/A | CUDAPm1 |
| AMD GPU | clLucas, gpuOwL | gpuOwL | Mfakto | N/A | N/A |
| Other CPUs (incl. ARM) | Mlucas | N/A | Mlucas | N/A | N/A |
The official GIMPS clients
- Main article: Prime95
Prime95/MPrime are free programs written by George Woltman and provided on his GIMPS site. To get started, just download the software, install it, and let it run. Simple and easy, but the road is long. GIMPS is not a project for the faint at heart, most of the exponents or work units, depending on type of work you choose to do, are huge! Over 86% of those who have begun to test a Mersenne exponent with GIMPS have never completed even one, and the average GIMPS participant has completed less than three (mean 2.67).
Prime95
Prime95 is the name of the Microsoft Windows based distributed client software written by George Woltman that is used by GIMPS, the distributed computing project researching Mersenne primes.
Prime95 became popular among PC enthusiasts and overclockers as its number-crunching algorithms exercise the computer's processor and memory to their limits. Recent versions of Prime95 include a torture test mode designed specifically for stressing PC subsystems.
MPrime
MPrime is the name of the Linux and BSD based distributed clients, written by George Woltman, that GIMPS, the distributed computing project researching Mersenne primes numbers, uses. It is entirely console-based, with no requirement for X or any other graphical sub-system.
Downloading
The Prime95 and Mprime clients can be downloaded from this page. These clients are easily installed and can be controlled using text files.
Latest versions
- Version 29.4 (released February 9, 2018) is the latest stable release.
About the clients
GIMPS appeals to those with a lot of patience, the work units take a lot of crunching, but pack serious punch. Very friendly to offline operation and P4's, and runs well on a wide range of x86 machines.
Finding a Mersenne prime is no easy task; a first time primality test for a single candidate exponent takes a fast machine three to four weeks, running 24/7. This is without a doubt one of most process intensive project in all of computing.
A test runs through three phases before the result is considered final, done gradually and by several different machines. First, each candidate exponent goes through a level of trial factoring, which is a brute force approach designed to eliminate non - prime candidates early on in the process. This works by checking the number for small divisors, using the fact that factors of Mersenne numbers are of the special form q = 2kp+1, and that testing a factor candidate simply requires a binary powering, i.e. one finds 2^p modulo q (which involves roughly log2(p) arithmetic steps on numbers no larger than q2) and checks if the result is equivalent to 1 modulo q. One can also do a small amount of factoring work using (say) Pollard's p-1 method or the elliptic curve method, both of which involve manipulating numbers the size of the Mersenne number itself. If no factors are found then the exponent is released for a first time Lucas-Lehmer test. A final double check is done later by another computer to verify the validity of the result.
This project has its advantages, namely the clients. This has to be the most stable, mature, feature rich DC client on the net. It will use as much or as little memory as you allow it, and will get completely out of the way whenever another program needs cycles. It can be run as a service, completely hidden from view, with the ability to run when the user logs off so no cycles are wasted.
Client highlights
- Mature client
- Easily runs when logged off. Just check Options/Start at Bootup. You need not know about Windows services!
- Caches work automatically, so it keeps going if offline. No helper programs are needed to cache work for it.
- Low memory needs so PCs with modest RAM can use it. If you are short on RAM you can still run it.
- Low bandwidth needs: <~1 kB / month. Great for dial-up!
- Stringent verification within each run and across runs, so you know your CPU cycles are not being wasted.
- GIMPS offers something that many other distributed projects do't: actual regular discoveries
- A very responsive developer, George Woltman
See also
External links
- www.mersenne.org - GIMPS home page
- www.mersenneforum.org - GIMPS forum
| General |
| Definitions |
| Work with GIMPS |
| Related |
| FAQ |
