Decimal Value of Mersenne Prime
 

I have an assembly program to calculate the actual value of a Mersenne Prime, given the exponent: start with 1, [double and add 1], ad libitum. IIRC it takes over a day on a single thread of a Core 2 Duo to produce the current largest Mersenne Prime.

Could that calculation be sped up appreciably using CUDA? (Or some other formula)?

Cheers.

mpz_pow()
mpz_out_str()
?

There are fast base conversion algorithms that make this process easy, assuming fast large-integer multiplication (see volume 2 of Knuth). I would think that for a 12-million digit number you could finish in less than a second.

Mprint does it very fast. I could not find an active link to the proper website, so I will attach it.

[QUOTE=vsuite;250772]I have an assembly program to calculate the actual value of a Mersenne Prime, given the exponent: start with 1, [double and add 1], ad libitum. IIRC it takes over a day on a single thread of a Core 2 Duo to produce the current largest Mersenne Prime.

Could that calculation be sped up appreciably using CUDA? (Or some other formula)?

Cheers.[/QUOTE]

That's a very inefficient algorithm. Better would be to do iterated squarings. Basically it is the [url=http://mersenne.org/various/math.php]algorithm for Trial Factorisation[/url] but without the "divide by the candidate factor and take the remainder" step.

[URL]http://en.wikipedia.org/wiki/Exponentiating_by_squaring#Squaring_algorithm[/URL]

...but of course mpz_pow() simply does that for you.

[QUOTE=Batalov;250868][URL]http://en.wikipedia.org/wiki/Exponentiating_by_squaring#Squaring_algorithm[/URL]

...but of course mpz_pow() simply does that for you.[/QUOTE]

There is no such function, you should use mpz_pow_ui(), or mpz_ui_pow_ui().
What is not in wikipedia article, that in some cases you can compute the power in linear time, for example the power 2^p.

Say you want to compute b^k, then gmp first searches the number of trailing bits of b, let this e, then b=2^e*u, where u is odd, and b^k=u^k*2^(e*k), this means that you need to compute *only* u^k then by an easy shift you can get b^k. If you apply this for the computation of 2^p then you will get this it in (optimal) linear time.

ps. obviously after the powering you need a mpz_sub_ui() also to get 2^p-1 Mersenne prime.

[QUOTE=vsuite;250772]I have an assembly program to calculate the actual value of a Mersenne Prime, given the exponent: start with 1, [double and add 1], ad libitum. IIRC it takes over a day on a single thread of a Core 2 Duo to produce the current largest Mersenne Prime.

Could that calculation be sped up appreciably using CUDA? (Or some other formula)?

Cheers.[/QUOTE]

couldn't this be sped up by a code that loops or a unrolled loop which adds a register holding a start value of 2 with itself. if this is continued the exponent amount of times, and followed by a subtraction. I also see other ways but I'm only basic in x86 asm and I haven't written a successful program.

The OP wanted to compute the decimal value of a Mersenne prime to full precision (millions of digits).

Even if you were a whiz with asm, you will not get his algorithm the thousands of times speedup to compete with using a better algorithm in the first place.

[QUOTE=jasonp;250885]The OP wanted to compute the decimal value of a Mersenne prime to full precision (millions of digits).

Even if you were a whiz with asm, you will not get his algorithm the thousands of times speedup to compete with using a better algorithm in the first place.[/QUOTE]

well if it could be extended I'd suggest f2xm1 as it calculates Mersenne numbers directly, by the sounds of it.

There's more than one way to skin a cat (e.g. trade base conversion for instead computing in an array of base 10[SUP]9[/SUP] 'digits'), but ... because the three-liner GMP-C program only takes a few seconds who [I]would[/I] want to spend more time writing a custom program?

[SIZE=1]->R. Gerbicz: yes, of course, you're right. There's an interesting google find about mpz_pow() absense (as a literal semantic)[/SIZE]
[SIZE=1]... and some of us even know who [I]Digital Parasite[/I] is.[/SIZE] :rolleyes: