mersenneforum.org Decimal Value of Mersenne Prime
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-02-01, 11:29 #1 vsuite   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.
 2011-02-01, 12:37 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23×7×163 Posts mpz_pow() mpz_out_str() ?
 2011-02-01, 13:26 #3 jasonp Tribal Bullet     Oct 2004 DA116 Posts 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.
2011-02-01, 15:47   #4
Uncwilly
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.
Attached Files
 mprintc5.zip (131.8 KB, 195 views)

2011-02-01, 18:15   #5
Mr. P-1

Jun 2003

7×167 Posts

Quote:
 Originally Posted by vsuite 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.
That's a very inefficient algorithm. Better would be to do iterated squarings. Basically it is the algorithm for Trial Factorisation but without the "divide by the candidate factor and take the remainder" step.

Last fiddled with by Mr. P-1 on 2011-02-01 at 18:16

 2011-02-01, 22:20 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23×7×163 Posts http://en.wikipedia.org/wiki/Exponen...ring_algorithm ...but of course mpz_pow() simply does that for you.
2011-02-01, 23:41   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts

Quote:
 Originally Posted by Batalov http://en.wikipedia.org/wiki/Exponen...ring_algorithm ...but of course mpz_pow() simply does that for you.
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.

Last fiddled with by R. Gerbicz on 2011-02-01 at 23:45

2011-02-02, 00:21   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by vsuite 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.
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.

 2011-02-02, 00:57 #9 jasonp 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.
2011-02-02, 01:40   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by jasonp 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.
well if it could be extended I'd suggest f2xm1 as it calculates Mersenne numbers directly, by the sounds of it.

 2011-02-02, 01:48 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 216508 Posts There's more than one way to skin a cat (e.g. trade base conversion for instead computing in an array of base 109 'digits'), but ... because the three-liner GMP-C 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 Corbyguy Software 3 2008-06-09 18:09 m_f_h Math 6 2007-02-16 13:43 illman-q Miscellaneous Math 33 2004-09-19 05:02 ixfd64 Math 2 2003-10-16 13:40

All times are UTC. The time now is 20:00.

Thu Oct 29 20:00:14 UTC 2020 up 49 days, 17:11, 2 users, load averages: 2.52, 2.91, 2.79