20110201, 11:29  #1 
Jan 2010
2×3×19 Posts 
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. 
20110201, 12:37  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
mpz_pow()
mpz_out_str() ? 
20110201, 13:26  #3 
Tribal Bullet
Oct 2004
DA1_{16} Posts 
There are fast base conversion algorithms that make this process easy, assuming fast largeinteger multiplication (see volume 2 of Knuth). I would think that for a 12million digit number you could finish in less than a second.

20110201, 15:47  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
8,747 Posts 
Mprint does it very fast. I could not find an active link to the proper website, so I will attach it.

20110201, 18:15  #5  
Jun 2003
7×167 Posts 
Quote:
Last fiddled with by Mr. P1 on 20110201 at 18:16 

20110201, 22:20  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
http://en.wikipedia.org/wiki/Exponen...ring_algorithm
...but of course mpz_pow() simply does that for you. 
20110201, 23:41  #7  
"Robert Gerbicz"
Oct 2005
Hungary
17·83 Posts 
Quote:
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^p1 Mersenne prime. Last fiddled with by R. Gerbicz on 20110201 at 23:45 

20110202, 00:21  #8  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:


20110202, 00:57  #9 
Tribal Bullet
Oct 2004
3·1,163 Posts 
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. 
20110202, 01:40  #10 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
well if it could be extended I'd suggest f2xm1 as it calculates Mersenne numbers directly, by the sounds of it.

20110202, 01:48  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
21650_{8} Posts 
There's more than one way to skin a cat (e.g. trade base conversion for instead computing in an array of base 10^{9} 'digits'), but ... because the threeliner GMPC program only takes a few seconds who would want to spend more time writing a custom program?
>R. Gerbicz: yes, of course, you're right. There's an interesting google find about mpz_pow() absense (as a literal semantic) ... and some of us even know who Digital Parasite is. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!  dabaichi  News  571  20201026 11:02 
Decimal Places  Corbyguy  Software  3  20080609 18:09 
decimal expression of mersenne candidates  m_f_h  Math  6  20070216 13:43 
The 40th known Mersenne prime, 2209960111 is not PRIME!  illmanq  Miscellaneous Math  33  20040919 05:02 
decimalbinary prime pairs  ixfd64  Math  2  20031016 13:40 