Save the following code in a file called mersenne.c:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
int main(int argc, char *argv[]) {
char *endptr;
unsigned long int p = strtoul(argv[1],&endptr,10);
mpz_t M, powerof2, one, two;
mpz_init(M); mpz_init(powerof2);
mpz_init_set_str(one,"1",10);
mpz_init_set_str(two,"2",10);
mpz_pow_ui(powerof2,two,p);
mpz_sub(M,powerof2,one);
gmp_printf("%Zd",M);
return 0;
}
Then compile and run it, like this:
Code:
$ gcc -o mersenne mersenne.c -lgmp
$ time ./mersenne 43112609 > M46
real 0m17.226s
user 0m16.874s
sys 0m0.163s
Note: You'll need the gmp-devel package installed to compile the code (at least version 4.2.x).
What this does is compute a
really big number, namely 2^43112609 - 1. This is the 46th
Mersenne prime, which is an integer with 12,978,189 digits.
The result above was on my 2.2GHz AMD64 3700+ (single-core) w/1GB PC3200 RAM, in Fedora 10 x86_64. I was wondering if 64-bit really would make a difference with this, and the answer seems to be yes. On my 32-bit Fedora system on the same machine it ran
much slower. So I'm curious to see how fast it runs on other people's computers, whether in a 32-bit or 64-bit OS.
The calculation of the number itself is almost instantaneous (comment out the gmp_printf statement if you want to see that). It's the printing of the result to stdout (which I redirected to the file M46) that takes a while. If anyone wants to try it with other Mersenne primes, look
here for a table of the known ones. For instance, to calculate the 37th Mersenne prime M37 = 2^3021377 - 1, do this:
Code:
time ./mersenne 3021377 > M37
In general, if you pass a positive integer N on the command line to the program, it will compute 2^N - 1. Since the numbers can be huge, I redirect the output to a file. You can see how many digits are in that file by running wc -c on it. By the way, to see the digits themselves, I don't recommend opening the output file M46 in a GUI editor like gedit. Either vi or emacs will open it much faster.
Did I do something wrong/right?
Hybrid Mode
