20181002, 19:09  #1 
Nov 2015
22_{8} Posts 
Fast primality funcion in a programming language
Hi everybody.
I am doing a test to find the fastest primality (or PRP) function in programming languages and tools. Testing the PRIME: p=31838235*2^34335+1 I get:  WInPFGW 3.7.7 32bit: 0'2"  LLR 3.7.1: 0'3"  (gmp lib) mpz_probab_prime(p,0): 0'17"  (Pari/GP): ispseudoprime(p,1): 0'27"  (Pari/GP): ispseudoprime(p): 1'24" PFGW is the fastest software, GMPLIB has the fastest programming function. Do you know faster languages or tools, expecially in programming languages? Thank you very much. Giovanni Di Maria 
20181002, 19:39  #2  
Sep 2002
Database er0rr
110110110001_{2} Posts 
Quote:
Code:
time ./pfgw64 k f0 od q"31838235*2^34335+1"  ../../coding/gwnum/prp2  31838235 2 34335 1 Is 2PRP! real 0m0.906s user 0m0.472s sys 0m0.020s Last fiddled with by paulunderwood on 20181002 at 19:43 

20181002, 19:58  #3 
Nov 2015
2·3^{2} Posts 

20181002, 20:21  #4  
Sep 2002
Database er0rr
5·701 Posts 
Quote:
Code:
ls gwnum/ giants.h gwcommon.h gwnum.a gwnum.h gwnum.ld gwthread.h Code:
gcc o prp2 prp2.c gwnum/gwnum.a gwnum/gwnum.ld lm lpthread lstdc++ ldl 

20181002, 21:18  #5 
Nov 2015
2×3^{2} Posts 
Thank you very very much!!!!!
Grazie. Giovanni 
20181003, 03:11  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001010_{2} Posts 
There is no one answer to your question of "the fastest primality function."
The fastest PRP test for very large numbers is using gwnum, hence PFGW or some other program using it (e.g. one of Paul's). The fastest proof software for large numbers is Primo (ECPP). Once you get into smaller sizes, there are many more choices. GMP is faster than gwnum below about 2000 digits. For 64bit results, my testing shows the C code in Perl's ntheory module to be faster than anything else, but I am biased. For proofs under ~500 digits, the BLS75+ECPP code from Perl/ntheory used to be fastest, but I have not tested with the latest Pari ECPP which might beat it (it definitely should as the size increases). Also be careful with your chosen number, as for example Perl/ntheory recognizes this as Proth form and so proves it faster than Pari/GP can run a single SPSP test. It uses GMP so isn't as fast as PFGW (and I assume it is slower than Penne's LLR). 
20181003, 03:46  #7 
Sep 2002
Database er0rr
3505_{10} Posts 

20181003, 03:53  #8 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·3·151 Posts 
Not offhand. I'll try to find time tomorrow to test if someone else does not first. Note that mpz_probab_prime silently does a base210 pseudoprime test first, so it really performs n+1 tests in terms of time cost.

20181003, 04:00  #9  
"Rashid Naimi"
Oct 2015
Remote to Here/There
11110011011_{2} Posts 
Quote:
Quote:
https://www.mersenneforum.org/showpo...6&postcount=42 Note: Replace the tabs in the code with spaces if you get run errors. Last fiddled with by a1call on 20181003 at 04:06 

20181003, 04:04  #10 
Nov 2015
2×3^{2} Posts 
Thank you to all!!!
Giovanni 
20181003, 15:20  #11 
Aug 2006
5,939 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Do normal adults give themselves an allowance? (...to fast or not to fast  there is no question!)  jasong  jasong  35  20161211 00:57 
Pretty Fast Primality Test (for numbers = 3 mod 4)  tapion64  Miscellaneous Math  40  20140420 05:43 
Which programming language i shall learn?  kakos22  Programming  4  20100812 12:02 
Primality searches and primality successes  marco_calabresi  Information & Answers  3  20090417 19:44 