Decimal Value of Mersenne Prime

vsuite · 2011-02-01, 11:29

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.

Batalov · 2011-02-01, 12:37

mpz_pow()
mpz_out_str()
?

jasonp · 2011-02-01, 13:26

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.

Uncwilly · 2011-02-01, 15:47

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

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

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.

Batalov · 2011-02-01, 22:20

http://en.wikipedia.org/wiki/Exponen...ring_algorithm

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

R. Gerbicz · 2011-02-01, 23:41

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.

science_man_88 · 2011-02-02, 00:21

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.

jasonp · 2011-02-02, 00:57

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.

science_man_88 · 2011-02-02, 01:40

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.

Batalov · 2011-02-02, 01:48

There's more than one way to skin a cat (e.g. trade base conversion for instead computing in an array of base 10⁹ '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.

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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!	dabaichi	News	571	2020-10-26 11:02
Decimal Places	Corbyguy	Software	3	2008-06-09 18:09
decimal expression of mersenne candidates	m_f_h	Math	6	2007-02-16 13:43
The 40th known Mersenne prime, 220996011-1 is not PRIME!	illman-q	Miscellaneous Math	33	2004-09-19 05:02
decimal-binary prime pairs	ixfd64	Math	2	2003-10-16 13:40

2011-02-01, 12:37	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 101² Posts	mpz_pow() mpz_out_str() ?

2011-02-01, 13:26	#3
jasonp Tribal Bullet Oct 2004 DED₁₆ 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, 22:20	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10011111011001₂ Posts	http://en.wikipedia.org/wiki/Exponen...ring_algorithm ...but of course mpz_pow() simply does that for you.

2011-02-02, 00:57	#9
jasonp Tribal Bullet Oct 2004 5×23×31 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:48	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10011111011001₂ 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⁹ '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.