mersenneforum.org Fast primality funcion in a programming language
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2018-10-03, 19:57   #12
paulunderwood

Sep 2002
Database er0rr

3,853 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?
Testing a 1000 rounds on a 1000 digit prime -- I will be testing numbers already sieved -- I get the following:

Code:
time ./gwnum_test

real	0m7.823s
user	0m7.860s
sys	0m0.004s
Code:
time ./GMP_test

real	0m13.058s
user	0m13.032s
sys	0m0.000s
Note that this is a comparison between a hand-rolled gwnum program and a GMP program using its mpz_powm() function.

 2019-01-26, 20:46 #13 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32·101 Posts Paul, Could you send or point me to your test programs? I'd like to run on my machine to compare identical programs. I was debating the merits of doing a comparison graph at different sizes, e.g. (1000+250n for n 0 to 12). A simple way would be creating a file with 100 or 1000 random primes of the given size, then time running a program that processes them all. E.g. PFGW with the file. That seems like a fairly realistic test of performance that removes most of the startup overhead. If you made a program that did some various tests (e.g. PRP, SPRP, BPSW and/or your tests) given a file with a number per line, would that seem like a good test? For very small inputs it would be worth pulling out even that overhead (e.g. read them all into an array of inputs, then start a timer around the testing, so we don't count overhead of I/O and string->bignum conversion).
2019-01-26, 22:56   #14
paulunderwood

Sep 2002
Database er0rr

3,853 Posts

Here you go.

Sorry for the messy code. I just hacked something together to do the comparison.
Attached Files
 AP8_version1.c (2.5 KB, 262 views) ap8_gmp.c (1.3 KB, 268 views)

Last fiddled with by paulunderwood on 2019-01-26 at 23:42

 2020-09-16, 09:15 #15 SethTro     "Seth" Apr 2019 22×7×13 Posts GMP 6.2.0 Improved mpz_probab_prime_p for both primes and composites. I measured the time vs pfgw over a range of inputs (200 to 160,000 bits) https://github.com/sethtroisi/misc-s...mbers-10p--379 For composites GMP is faster till ~4000 bits and ~3x slower by 90,000 bits. For primes GMP performs more a full Baillie-PSW primality test and takes ~5x longer. It's slower on small primes (500 bits) and 10x slower by 15,000 bits.
2020-09-24, 00:30   #16
paulunderwood

Sep 2002
Database er0rr

3,853 Posts

Quote:
 Power Numbers (10^P + {3,7,9}) NOTE: GMP performs multiple tests for primality not just 3-PRP (hence longer runtime for primes)
I don't think GMP switch to special k*b^n+-c like PFGW's implementation of GWNUM.

Also PFGW uses GMP below a certain threshold.

If GMP has improved PRP times then maybe the author, "rogue", should realise it in the next release of PFGW.

 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 17:17.

Sun Oct 17 17:17:26 UTC 2021 up 86 days, 11:46, 1 user, load averages: 1.94, 2.10, 1.97