mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2018-10-02, 19:09   #1
calimero22
 
Nov 2015

100102 Posts
Default 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
calimero22 is offline   Reply With Quote
Old 2018-10-02, 19:39   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

Quote:
Originally Posted by calimero22 View Post
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
paulunderwood is offline   Reply With Quote
Old 2018-10-02, 19:58   #3
calimero22
 
Nov 2015

1810 Posts
Default

Hi paulunderwood

GREAT !!!!
Thank you. I will study to implement it.
Thank you.
Giovanni
calimero22 is offline   Reply With Quote
Old 2018-10-02, 20:21   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101011101102 Posts
Default

Quote:
Originally Posted by calimero22 View Post
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
File Type: zip prp2.c.zip (1.0 KB, 66 views)
paulunderwood is offline   Reply With Quote
Old 2018-10-02, 21:18   #5
calimero22
 
Nov 2015

1810 Posts
Default

Thank you very very much!!!!!
Grazie.
Giovanni
calimero22 is offline   Reply With Quote
Old 2018-10-03, 03:11   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

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).
danaj is offline   Reply With Quote
Old 2018-10-03, 03:46   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

65668 Posts
Default

Thanks for the survey, Dana.

Quote:
Originally Posted by danaj View Post
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?
paulunderwood is offline   Reply With Quote
Old 2018-10-03, 03:53   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
danaj is offline   Reply With Quote
Old 2018-10-03, 04:00   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

41·47 Posts
Default

Quote:
Originally Posted by calimero22 View Post
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
a1call is offline   Reply With Quote
Old 2018-10-03, 04:04   #10
calimero22
 
Nov 2015

2·32 Posts
Default

Thank you to all!!!
Giovanni
calimero22 is offline   Reply With Quote
Old 2018-10-03, 15:20   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593010 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
CRGreathouse is offline   Reply With Quote
Reply

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 2018-03-11 23:20
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
Pretty Fast Primality Test (for numbers = 3 mod 4) tapion64 Miscellaneous Math 40 2014-04-20 05:43
Which programming language i shall learn? kakos22 Programming 4 2010-08-12 12:02
Primality searches and primality successes 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

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.