mersenneforum.org Fast primality funcion in a programming language
 Register FAQ Search Today's Posts Mark Forums Read

 2018-10-02, 19:09 #1 calimero22   Nov 2015 100102 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
2018-10-02, 19:39   #2
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

Quote:
 Originally Posted by calimero22 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
The fastest library in town for numbers of this size is muti-threaded gwnum, the library behind PFGW/LLR/Prime95. For example, running at 3.6GHz on a Haswell i7, I have written a C program using the latest gwnum library:

Code:
time ./pfgw64 -k -f0 -od -q"31838235*2^34335+1" | ../../coding/gwnum/prp2 - 31838235 2 34335 1

Is 2-PRP!

real	0m0.906s
user	0m0.472s
sys	0m0.020s

Last fiddled with by paulunderwood on 2018-10-02 at 19:43

 2018-10-02, 19:58 #3 calimero22   Nov 2015 1810 Posts Hi paulunderwood GREAT !!!! Thank you. I will study to implement it. Thank you. Giovanni
2018-10-02, 20:21   #4
paulunderwood

Sep 2002
Database er0rr

1101011101102 Posts

Quote:
 Originally Posted by calimero22 Hi paulunderwood GREAT !!!! Thank you. I will study to implement it. Thank you. Giovanni
It is a bit tricky. You have to download Prime95 and compile the appropriate part of its source suited to your architecture. I then copy the following files to the subdirectory of my program:

Code:
 ls gwnum/
giants.h  gwcommon.h  gwnum.a  gwnum.h  gwnum.ld  gwthread.h
Then I compile with:

Code:
gcc -o prp2 prp2.c gwnum/gwnum.a gwnum/gwnum.ld -lm -lpthread -lstdc++ -ldl
By studying gwnum.h you can add round off error checking to this attached program.
Attached Files
 prp2.c.zip (1.0 KB, 66 views)

 2018-10-02, 21:18 #5 calimero22   Nov 2015 1810 Posts Thank you very very much!!!!! Grazie. Giovanni
 2018-10-03, 03:11 #6 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 16128 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 64-bit 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).
2018-10-03, 03:46   #7
paulunderwood

Sep 2002
Database er0rr

65668 Posts

Thanks for the survey, Dana.

Quote:
 Originally Posted by danaj GMP is faster than gwnum below about 2000 digits.
Do you know how much faster GMP's mpz_probab_prime() is over gwnum at 1000 digits for general numbers?

2018-10-03, 03:53   #8
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts

Quote:
 Originally Posted by paulunderwood Do you know how much faster GMP's mpz_probab_prime() is over gwnum at 1000 digits for general numbers?
Not off-hand. I'll try to find time tomorrow to test if someone else does not first. Note that mpz_probab_prime silently does a base-210 pseudoprime test first, so it really performs n+1 tests in terms of time cost.

2018-10-03, 04:00   #9
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

41·47 Posts

Quote:
 Originally Posted by calimero22 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
This might be relevant:

Quote:
 Here's some very simple code to perform a strong probable-prime test. (With a random base this is the Miller-Rabin test.)
It is quite a fast PRP test, much faster than the built-in ispseudoprime() in PARI-GP.

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 2018-10-03 at 04:06

 2018-10-03, 04:04 #10 calimero22   Nov 2015 2·32 Posts Thank you to all!!! Giovanni
2018-10-03, 15:20   #11
CRGreathouse

Aug 2006

593010 Posts

Quote:
 Originally Posted by a1call It is quite a fast PRP test, much faster than the built-in ispseudoprime() in PARI-GP.
Naturally -- BPSW takes 3 times as long as MR on a prime.

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 jasong jasong 35 2016-12-11 00:57 tapion64 Miscellaneous Math 40 2014-04-20 05:43 kakos22 Programming 4 2010-08-12 12:02 marco_calabresi Information & Answers 3 2009-04-17 19:44

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

Sat Oct 24 04:11:28 UTC 2020 up 44 days, 1:22, 1 user, load averages: 1.81, 1.58, 1.45