mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2015-02-05, 16:32   #1
FreakyPotato
 
Feb 2015

110 Posts
Default Primorial calculation

Hello,
I'd like to know if there is any fast way to compute primorial numbers, the regular way of multiplying the primorial by the following prime is taking too long and I need to compute really large primorials. A list with some large primorials where I can check would also work fine.
I already have a list up to 239439#
FreakyPotato is offline   Reply With Quote
Old 2015-02-05, 17:00   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D1116 Posts
Default

Quote:
Originally Posted by FreakyPotato View Post
Hello,
I'd like to know if there is any fast way to compute primorial numbers, the regular way of multiplying the primorial by the following prime is taking too long and I need to compute really large primorials. A list with some large primorials where I can check would also work fine.
I already have a list up to 239439#
Use GMP... specifically: mpz_primorial_ui

https://gmplib.org/manual/Number-The...etic-Functions
bsquared is offline   Reply With Quote
Old 2015-02-05, 17:24   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·19·179 Posts
Default

Quote:
Originally Posted by bsquared View Post
Use GMP... specifically: mpz_primorial_ui

https://gmplib.org/manual/Number-The...etic-Functions
We have a different idea as what constitutes "fast".

In my view no fast way is known. If there were, we'd have a fast way of factoring general integers.

Consider gcde(N, m#) for appropriate values of m
xilman is online now   Reply With Quote
Old 2015-02-05, 19:00   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×5×223 Posts
Default

Quote:
Originally Posted by xilman View Post
We have a different idea as what constitutes "fast".

In my view no fast way is known. If there were, we'd have a fast way of factoring general integers.

Consider gcde(N, m#) for appropriate values of m
I guess we have a different interpretation of what the OP meant as "large". He gave an example of having computed 239439# but being able to go no further using the naive method 2*3*5*...*pn. GMP is certainly able to compute inputs several orders of magnitude larger, using "fast" methods such as divide and conquer together with sub-quadratic multiplication. But several orders of magnitude larger than 239439 is still useless for factoring general numbers; I'm not trying to suggest GMP can do that.
bsquared is offline   Reply With Quote
Old 2015-02-05, 21:36   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

The simple answer is just as was said earlier: use mpz_primorial_ui(res, n). It uses a sieve and an internal single-limb product tree. It's pretty fast.

If you really want to do it yourself, first you will want some way to get primes at a reasonable speed. Use a sieve -- certainly don't use mpz_nextprime() as it is quite slow. Second, you will want to use some sort of product tree. Even a simple 16-bucket shallow tree will get you 10x speedup. As you get into the millions, you need to go deeper or just use the builtin.

If you don't want to program, you can get CRG's Pari extensions which should give reasonable speed (I haven't benchmarked). Perl's 'ntheory' module gives reasonably fast primorials if you have the GMP library (next release should be faster for 1M+ inputs) and is easy to use from the shell. I'm sure there are other packages that work well.
danaj is offline   Reply With Quote
Old 2015-02-05, 23:42   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

BTW, mpz_primorial_ui was added in GMP 5.1 (Dec 2012). For best performance, get the newest GMP code you can (6.0.0a right now).
danaj is offline   Reply With Quote
Old 2015-02-06, 05:03   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001100102 Posts
Default

Quote:
Originally Posted by xilman View Post
We have a different idea as what constitutes "fast".

In my view no fast way is known. If there were, we'd have a fast way of factoring general integers.
What kind of output do you allow? If you output, e.g., the binary representation then the length of the output is exponential in the input size, so the time needed just to write the answer is longer than the time for trial division. If you allow a compact representation of the output it may be doable, but at the other extreme you'd just copy the input with a "#" at the end.
CRGreathouse is offline   Reply With Quote
Old 2015-02-06, 10:33   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

237338 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
What kind of output do you allow? If you output, e.g., the binary representation then the length of the output is exponential in the input size, so the time needed just to write the answer is longer than the time for trial division. If you allow a compact representation of the output it may be doable, but at the other extreme you'd just copy the input with a "#" at the end.
I would like an algorithm which generates m# mod N in time polynomial in the sizes of the inputs.

Last fiddled with by xilman on 2015-02-06 at 10:34
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Largest Known Primorial a1call Miscellaneous Math 11 2016-12-14 21:35
Riesel Primorial k Search Merfighters Open Projects 1 2010-07-29 14:52
primorial primes jasong Math 1 2006-08-12 01:38
Primorial puzzle Citrix Puzzles 3 2006-03-07 15:07
Primorial question Dougy Math 2 2005-07-28 13:13

All times are UTC. The time now is 11:07.

Tue Dec 1 11:07:12 UTC 2020 up 82 days, 8:18, 1 user, load averages: 1.13, 1.22, 1.37

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.