20150205, 16:32  #1 
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# 
20150205, 17:00  #2  
"Ben"
Feb 2007
6346_{8} Posts 
Quote:
https://gmplib.org/manual/NumberThe...eticFunctions 

20150205, 17:24  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·11·307 Posts 
Quote:
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 

20150205, 19:00  #4 
"Ben"
Feb 2007
2×13×127 Posts 
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 subquadratic 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.

20150205, 21:36  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
38A_{16} Posts 
The simple answer is just as was said earlier: use mpz_primorial_ui(res, n). It uses a sieve and an internal singlelimb 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 16bucket 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. 
20150205, 23:42  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 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).

20150206, 05:03  #7 
Aug 2006
1011100101101_{2} Posts 
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.

20150206, 10:33  #8  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·11·307 Posts 
Quote:
Last fiddled with by xilman on 20150206 at 10:34 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Largest Known Primorial  a1call  Miscellaneous Math  11  20161214 21:35 
Riesel Primorial k Search  Merfighters  Open Projects  1  20100729 14:52 
primorial primes  jasong  Math  1  20060812 01:38 
Primorial puzzle  Citrix  Puzzles  3  20060307 15:07 
Primorial question  Dougy  Math  2  20050728 13:13 