mersenneforum.org Primorial calculation
 Register FAQ Search Today's Posts Mark Forums Read

 2015-02-05, 16:32 #1 FreakyPotato   Feb 2015 1 Posts 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#
2015-02-05, 17:00   #2
bsquared

"Ben"
Feb 2007

3·1,193 Posts

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

2015-02-05, 17:24   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

3·13·283 Posts

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

2015-02-05, 19:00   #4
bsquared

"Ben"
Feb 2007

3×1,193 Posts

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

 2015-02-05, 21:36 #5 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38D16 Posts 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.
 2015-02-05, 23:42 #6 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32×101 Posts 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).
2015-02-06, 05:03   #7
CRGreathouse

Aug 2006

135338 Posts

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

2015-02-06, 10:33   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

254358 Posts

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

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

All times are UTC. The time now is 21:49.

Wed Dec 8 21:49:14 UTC 2021 up 138 days, 16:18, 0 users, load averages: 1.82, 1.64, 1.63