mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2018-10-03, 19:57   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

344610 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?
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.
paulunderwood is offline   Reply With Quote
Old 2019-01-26, 20:46   #13
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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).
danaj is offline   Reply With Quote
Old 2019-01-26, 22:56   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

Here you go.

Sorry for the messy code. I just hacked something together to do the comparison.
Attached Files
File Type: c AP8_version1.c (2.5 KB, 67 views)
File Type: c ap8_gmp.c (1.3 KB, 71 views)

Last fiddled with by paulunderwood on 2019-01-26 at 23:42
paulunderwood is offline   Reply With Quote
Old 2020-09-16, 09:15   #15
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

B516 Posts
Default

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.
SethTro is offline   Reply With Quote
Old 2020-09-24, 00:30   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

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.
paulunderwood 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 03:43.

Sat Oct 24 03:43:20 UTC 2020 up 44 days, 54 mins, 1 user, load averages: 1.21, 1.28, 1.34

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.