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

[QUOTE=enzocreti;506755]Are there C programs or libraries allowing probable primes tests for very large numbers (100k+ digits)?
Thanks[/QUOTE]

At "100k+ digits" there is GWNUM, but why bother when you can use OpenPFGW? :smile:

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.

compiler
 

[QUOTE=danaj;506796]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.[/QUOTE]
thanks

and a compiler for C? What do you suggest?

PERL
 

What about ispseudoprime(a,b) function in Perl? Is it fast?

[QUOTE=enzocreti;506819]thanks

and a compiler for C? What do you suggest?[/QUOTE]
Maybe I'm misunderstanding the question, but gcc of course.

[QUOTE=enzocreti;506819]thanks

and a compiler for C? What do you suggest?[/QUOTE]

There is a build of pfgw already available on sourceforge. You don't need to compile it.

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 [SIZE="1"]517216668078912555...019387837939836679416522197[/SIZE]

[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[/CODE]

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][/CODE]

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)[/CODE]

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)[/CODE]

[QUOTE=danaj;506853]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 [SIZE="1"]517216668078912555...019387837939836679416522197[/SIZE]

[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[/CODE]

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.
[/QUOTE]

@Dana. [URL="https://www.mersenneforum.org/showthread.php?t=23687&page=2"]I ran 1000 rounds[/URL] 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?

[QUOTE=paulunderwood;506857]@Dana. [URL="https://www.mersenneforum.org/showthread.php?t=23687&page=2"]I ran 1000 rounds[/URL] 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![/quote]It is quite possible.

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

[FONT="Courier New"]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);'[/FONT]

Single invocations, again 100 loops:
[FONT="Courier New"]0.80s ./pfgw64s with input file
0.73s Perl with a loop[/FONT]

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.