mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2011-02-01, 11:29   #1
vsuite
 
Jan 2010

1628 Posts
Default 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.
vsuite is offline   Reply With Quote
Old 2011-02-01, 12:37   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

237916 Posts
Default

mpz_pow()
mpz_out_str()
?
Batalov is offline   Reply With Quote
Old 2011-02-01, 13:26   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,527 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-02-01, 15:47   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

20DF16 Posts
Default

Mprint does it very fast. I could not find an active link to the proper website, so I will attach it.
Attached Files
File Type: zip mprintc5.zip (131.8 KB, 158 views)
Uncwilly is online now   Reply With Quote
Old 2011-02-01, 18:15   #5
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

49116 Posts
Default

Quote:
Originally Posted by vsuite View Post
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
Mr. P-1 is offline   Reply With Quote
Old 2011-02-01, 22:20   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

908110 Posts
Default

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

...but of course mpz_pow() simply does that for you.
Batalov is offline   Reply With Quote
Old 2011-02-01, 23:41   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

25428 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2011-02-02, 00:21   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by vsuite View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-02-02, 00:57   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,527 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-02-02, 01:40   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-02-02, 01:48   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32·1,009 Posts
Default

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.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 561 2013-03-29 16:55
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

All times are UTC. The time now is 04:54.

Tue Aug 11 04:54:37 UTC 2020 up 25 days, 41 mins, 1 user, load averages: 3.28, 3.17, 2.95

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.