mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > enzocreti

Reply
 
Thread Tools
Old 2019-01-24, 12:31   #1
enzocreti
 
Mar 2018

7758 Posts
Default Programs and libraries in C for testing prp

Are there C programs or libraries allowing probable primes tests for very large numbers (100k+ digits)?
Thanks
enzocreti is offline   Reply With Quote
Old 2019-01-24, 16:23   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

CC516 Posts
Default

Quote:
Originally Posted by enzocreti View Post
Are there C programs or libraries allowing probable primes tests for very large numbers (100k+ digits)?
Thanks
At "100k+ digits" there is GWNUM, but why bother when you can use OpenPFGW?
paulunderwood is offline   Reply With Quote
Old 2019-01-24, 20:02   #3
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

Lots of programs that support big numbers should work. My libraries using GMP work fine. But ..... at 100k+ digits they are quite a bit slower than gwnum. As Paul said, it's easiest to use OpenPFGW to start. If it comes back with a positive result you can use one of the other libraries to churn through another test (e.g. BPSW) if that's something you want.
danaj is offline   Reply With Quote
Old 2019-01-25, 06:56   #4
enzocreti
 
Mar 2018

509 Posts
Default compiler

Quote:
Originally Posted by danaj View Post
Lots of programs that support big numbers should work. My libraries using GMP work fine. But ..... at 100k+ digits they are quite a bit slower than gwnum. As Paul said, it's easiest to use OpenPFGW to start. If it comes back with a positive result you can use one of the other libraries to churn through another test (e.g. BPSW) if that's something you want.
thanks

and a compiler for C? What do you suggest?
enzocreti is offline   Reply With Quote
Old 2019-01-25, 08:22   #5
enzocreti
 
Mar 2018

509 Posts
Default PERL

What about ispseudoprime(a,b) function in Perl? Is it fast?
enzocreti is offline   Reply With Quote
Old 2019-01-25, 12:04   #6
M344587487
 
M344587487's Avatar
 
"Composite as Heck"
Oct 2017

10010010102 Posts
Default

Quote:
Originally Posted by enzocreti View Post
thanks

and a compiler for C? What do you suggest?
Maybe I'm misunderstanding the question, but gcc of course.
M344587487 is offline   Reply With Quote
Old 2019-01-25, 14:14   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10110100110102 Posts
Default

Quote:
Originally Posted by enzocreti View Post
thanks

and a compiler for C? What do you suggest?
There is a build of pfgw already available on sourceforge. You don't need to compile it.
rogue is offline   Reply With Quote
Old 2019-01-25, 21:37   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38616 Posts
Default

These are timings in seconds from my i6700K running Linux. Your mileage may vary. The speed difference is pretty dramatic, which is why everyone recommends using PFGW to start for big inputs.

1000 digit random prime 517216668078912555...019387837939836679416522197

Code:
  0.0337   PRP  PFGW 3.8.3 -Cquiet -k -u0 -f0 -q
  0.0073   PRP  Perl/ntheory is_pseudoprime($n,3)

  0.0073  SPRP  Perl/ntheory is_strong_pseudoprime($n,3)
  0.0083  SPRP  Pari/GP 2.12 ispseudoprime(n,1)

  0.0233  BPSW  Perl/ntheory is_bpsw_prime($n)
  0.0233  BPSW  Pari/GP 2.12 ispseudoprime(n)

 97.2  ECPP  Pari/GP 2.12 isprime(n)  \\ ECPP was used for this input
152.6   APR  Pari/GP 2.12 isprime(n,2)
203.4  ECPP  ecpp-dj 1.04
An aside here that Pari/GP's ECPP now easily beats my ECPP implementation. At 1000 digits, PFGW doesn't run as fast as the programs using GMP.

3443 digits 305136484659*2^11399-1

Code:
  0.06   PRP  PFGW 3.8.3 -Cquiet -k -u0 -f0 -q
  0.18   PRP  Perl/ntheory is_pseudoprime($n,3)

  0.18  SPRP  Perl/ntheory is_strong_pseudoprime($n,3)
  0.21  SPRP  Pari/GP 2.12 ispseudoprime(n,1)

  0.38  BPSW  Perl/ntheory is_bpsw_prime($n)
  0.40  BPSW  Pari/GP 2.12 ispseudoprime(n)

  0.23   LLR  Perl/ntheory is_prime [recognizes LLR form, uses its LLR proof code]
  0.23   LLR  Perl/ntheory is_provable_prime [same as above]
32523 digits 1124044292325*2^107999-1

Code:
    3.6  PFGW 3.8.3 3-PRP
   45.1  Perl/ntheory is_pseudoprime($n,3)

   45.0  Perl/ntheory is_strong_pseudoprime($n,3)
   46.9  Pari/GP 2.12 ispseudoprime(n,1)

  105.8  Perl/ntheory is_bpsw_prime($n)
  121.4  Pari/GP 2.12 ispseudoprime(n)
79911 digits 183027*2^265440-1

Code:
   19.1  PFGW 3.8.3 3-PRP
  363.9  Perl/ntheory is_pseudoprime($n,3)

  362.0  Perl/ntheory is_strong_pseudoprime($n,3)
  395.5  Pari/GP 2.12 ispseudoprime(n,1)

  840.1  Perl/ntheory is_bpsw_prime($n)
  961.8  Pari/GP 2.12 ispseudoprime(n)
danaj is offline   Reply With Quote
Old 2019-01-25, 21:55   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

7×467 Posts
Default

Quote:
Originally Posted by danaj View Post
These are timings in seconds from my i6700K running Linux. Your mileage may vary. The speed difference is pretty dramatic, which is why everyone recommends using PFGW to start for big inputs.

1000 digit random prime 517216668078912555...019387837939836679416522197

Code:
  0.0337   PRP  PFGW 3.8.3 -Cquiet -k -u0 -f0 -q
  0.0073   PRP  Perl/ntheory is_pseudoprime($n,3)

  0.0073  SPRP  Perl/ntheory is_strong_pseudoprime($n,3)
  0.0083  SPRP  Pari/GP 2.12 ispseudoprime(n,1)

  0.0233  BPSW  Perl/ntheory is_bpsw_prime($n)
  0.0233  BPSW  Pari/GP 2.12 ispseudoprime(n)

 97.2  ECPP  Pari/GP 2.12 isprime(n)  \\ ECPP was used for this input
152.6   APR  Pari/GP 2.12 isprime(n,2)
203.4  ECPP  ecpp-dj 1.04
An aside here that Pari/GP's ECPP now easily beats my ECPP implementation. At 1000 digits, PFGW doesn't run as fast as the programs using GMP.
@Dana. I ran 1000 rounds of GMP vs. GWNUM on a 4770k at 1000 digits and obtained a completely different timing ratio to yours above. Maybe your ratio is explained by the fire-up time of PFGW!

When I have run incremental n searches with PFGW in the past I am pretty sure GMP is used for numbers less than 300 digits. Or was it 600 digits?

Last fiddled with by paulunderwood on 2019-01-25 at 22:00
paulunderwood is offline   Reply With Quote
Old 2019-01-26, 04:50   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90210 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
@Dana. I ran 1000 rounds of GMP vs. GWNUM on a 4770k at 1000 digits and obtained a completely different timing ratio to yours above. Maybe your ratio is explained by the fire-up time of PFGW!
It is quite possible.

Run inside: time for i in `seq 1 100`; do XXX; done for these XXX:

3.252s ./pfgw64s -k -Cquiet -f0 -u0 -q'...'
2.675s ./prp2 t.txt
1.917s perl -le 'use ntheory qw/:all/; print is_strong_pseudoprime("...",3);'


Single invocations, again 100 loops:
0.80s ./pfgw64s with input file
0.73s Perl with a loop


It looks like gwnum has quite a bit of startup overhead, even compared to firing up Perl. PFGW has even more. But once going PFGW seems to be running nearly the same speed on this machine. I tried base 2 and both strong and normal pseudoprime tests just in case that had some impact.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU Testing programs nucleon GPU Computing 5 2011-08-21 04:24
suggestion: separation of libraries ixfd64 Software 10 2011-01-20 23:02
Interested in C/C++ libraries for factoring PythonPower Factoring 27 2009-05-28 17:08
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53
Large Integer Libraries andi314 Programming 18 2004-06-21 22:37

All times are UTC. The time now is 08:07.

Sun Jul 5 08:07:00 UTC 2020 up 102 days, 5:40, 1 user, load averages: 0.83, 1.20, 1.19

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.