This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.20
in repository libmath-prime-util-perl.
commit cccb050bbf791def1b38b7b47e3a9198f260e804
Author: Dana Jacobsen <d...@acm.org>
Date: Sat Feb 2 17:19:30 2013 -0800
Speedup for PP AKS, turn off tests on 32-bit machines
---
Changes | 4 +
Makefile.PL | 16 ++--
TODO | 2 +
lib/Math/Prime/Util.pm | 225 ++++++++++++++++++++++++++++++++--------------
lib/Math/Prime/Util/PP.pm | 37 ++++----
t/80-pp.t | 5 +-
6 files changed, 199 insertions(+), 90 deletions(-)
diff --git a/Changes b/Changes
index 36ca504..904b316 100644
--- a/Changes
+++ b/Changes
@@ -1,5 +1,9 @@
Revision history for Perl extension Math::Prime::Util.
+0.20 2 February 2012
+
+ - Little speedup for PP AKS, and turn off test on 32-bit machines.
+
0.19 1 February 2012
- Update MR bases with newest from http://miller-rabin.appspot.com/.
diff --git a/Makefile.PL b/Makefile.PL
index a89dd6a..4d58a9c 100644
--- a/Makefile.PL
+++ b/Makefile.PL
@@ -33,12 +33,16 @@ WriteMakefile1(
'Math::BigFloat' => '1.59',
},
META_MERGE => {
- recommends => {
- 'Math::Prime::Util::GMP' => 0.06,
- 'Math::BigInt::GMP' => 0,
- 'Math::MPFR' => 2.03,
- },
- },
+ resources => {
+ homepage => 'https://github.com/danaj/Math-Prime-Util',
+ repository => 'https://github.com/danaj/Math-Prime-Util',
+ },
+ recommends => {
+ 'Math::Prime::Util::GMP' => 0.06,
+ 'Math::BigInt::GMP' => 0,
+ 'Math::MPFR' => 2.03,
+ },
+ },
MIN_PERL_VERSION => 5.006002,
);
diff --git a/TODO b/TODO
index f960009..5477e1b 100644
--- a/TODO
+++ b/TODO
@@ -47,3 +47,5 @@
- Perfect power from Dietzfelbinger algorithm 2.3.5 works a bit better.
Newton's method would be even better.
+
+- Add PE 35 Circular primes and PE 291 Panatoipal primes to bin/primes.pl
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index b5061f8..5d1bb5e 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -1979,26 +1979,32 @@ If you are using bigints, here are some performance
suggestions:
=over 4
-=item Install L<Math::Prime::Util::GMP>, as that will vastly increase the
- speed of many of the functions. This does require the
- L<GMP|gttp://gmplib.org> library be installed on your system, but this
- increasingly comes pre-installed or easily available using the OS vendor
- package installation tool.
-
-=item Install and use L<Math::BigInt::GMP> or L<Math::BigInt::Pari>, then use
- C<use bigint try =E<gt> 'GMP,Pari'> in your script, or on the command
- line C<-Mbigint=lib,GMP>. Large modular exponentiation is much faster
- using the GMP or Pari backends, as are the math and approximation
- functions when called with very large inputs.
-
-=item Install L<Math::MPFR> if you use the Ei, li, Zeta, or R functions. If
- that module can be loaded, these functions will run much faster on
- bignum inputs, and are able to provide higher accuracy.
-
-=item Having run these functions on many versions of Perl, if you're using
- anything older than Perl 5.14, I would recommend you upgrade if you
- are using bignums a lot. There are some brittle behaviors on
- 5.12.4 and earlier with bignums.
+=item *
+
+Install L<Math::Prime::Util::GMP>, as that will vastly increase the speed
+of many of the functions. This does require the L<GMP|gttp://gmplib.org>
+library be installed on your system, but this increasingly comes
+pre-installed or easily available using the OS vendor package installation
tool.
+
+=item *
+
+Install and use L<Math::BigInt::GMP> or L<Math::BigInt::Pari>, then use
+C<use bigint try =E<gt> 'GMP,Pari'> in your script, or on the command line
+C<-Mbigint=lib,GMP>. Large modular exponentiation is much faster using the
+GMP or Pari backends, as are the math and approximation functions when
+called with very large inputs.
+
+=item *
+
+Install L<Math::MPFR> if you use the Ei, li, Zeta, or R functions. If that
+module can be loaded, these functions will run much faster on bignum inputs,
+and are able to provide higher accuracy.
+
+=item *
+
+Having run these functions on many versions of Perl, if you're using anything
+older than Perl 5.14, I would recommend you upgrade if you are using bignums
+a lot. There are some brittle behaviors on 5.12.4 and earlier with bignums.
=back
@@ -2915,13 +2921,65 @@ Print some primes above 64-bit range:
# perl -MMath::Pari=:int,PARI,nextprime -E 'my $start = PARI
"100000000000000000000"; my $end = $start+1000; my $p=nextprime($start); while
($p <= $end) { say $p; $p = nextprime($p+1); }'
-Project Euler, problem 10. Solution in under 50 milliseconds:
+Project Euler, problem 3 (Largest prime factor):
+
+ use Math::Prime::Util qw/factor/;
+ use bigint; # Only necessary for 32-bit machines.
+ say "", (factor(600851475143))[-1]
+
+Project Euler, problem 7 (10001st prime):
+
+ use Math::Prime::Util qw/nth_prime/;
+ say nth_prime(10_001);
+
+Project Euler, problem 10 (summation of primes):
use Math::Prime::Util qw/primes/;
my $sum = 0;
$sum += $_ for @{primes(2_000_000)};
say $sum;
+Project Euler, problem 21 (Amicable numbers):
+
+ use Math::Prime::Util qw/divisor_sum/;
+ sub dsum { my $n = shift; divisor_sum($n, sub {$_[0]}) - $n; }
+ my $sum = 0;
+ foreach my $a (1..10000) {
+ my $b = dsum($a);
+ $sum += $a + $b if $b > $a && dsum($b) == $a;
+ }
+ say $sum;
+
+Project Euler, problem 41 (Pandigital prime), brute force command line:
+
+ perl -MMath::Prime::Util=:all -E 'my @p = grep {
/1/&&/2/&&/3/&&/4/&&/5/&&/6/&&/7/} @{primes(1000000,9999999)}; say $p[-1];
+
+Project Euler, problem 47 (Distinct primes factors):
+
+ use Math::Prime::Util qw/factor/;
+ use List::MoreUtils qw/distinct/;
+ sub nfactors { scalar distinct factor(shift); }
+ my $n = pn_primorial(4); # Start with the first 4-factor number
+ $n++ while (nfactors($n) != 4 || nfactors($n+1) != 4 || nfactors($n+2) != 4
|| nfactors($n+3) != 4);
+ say $n;
+
+Project Euler, problem 69, stupid brute force solution (about 5 seconds):
+
+ use Math::Prime::Util qw/euler_phi/;
+ my ($n, $max) = (0,0);
+ do {
+ my $ndivphi = $_/euler_phi($_);
+ ($n, $max) = ($_, $ndivphi) if $ndivphi > $max;
+ } for 1..1000000;
+ say "$n $max";
+
+Here's the right way to do PE problem 69 (under 0.03s):
+
+ use Math::Prime::Util qw/pn_primorial/;
+ my $n = 0;
+ $n++ while pn_primorial($n+1) < 1000000;
+ say pn_primorial($n);'
+
=head1 LIMITATIONS
@@ -2977,14 +3035,15 @@ Perl modules, counting the primes to C<800_000_000>
(800 million):
--------- -------------------------- ------- -----------
0.03 Math::Prime::Util 0.12 using Lehmer's method
0.28 Math::Prime::Util 0.17 segmented mod-30 sieve
- 0.52 Math::Prime::Util::PP 0.14 Perl (Lehmer's method)
+ 0.47 Math::Prime::Util::PP 0.14 Perl (Lehmer's method)
0.9 Math::Prime::Util 0.01 mod-30 sieve
2.9 Math::Prime::FastSieve 0.12 decent odd-number sieve
11.7 Math::Prime::XS 0.29 "" but needs a count API
15.0 Bit::Vector 7.2
- 57.3 Math::Prime::Util::PP 0.14 Perl (fastest I know of)
+ 48.9 Math::Prime::Util::PP 0.14 Perl (fastest I know of)
170.0 Faster Perl sieve (net) 2012-01 array of odds
548.1 RosettaCode sieve (net) 2012-06 simplistic Perl
+ 3048.1 Math::Primality 0.08 Perl + Math::GMPz
~11000 Math::Primality 0.04 Perl + Math::GMPz
>20000 Math::Big 1.12 Perl, > 26GB RAM used
@@ -3017,38 +3076,46 @@ The differences are in the implementations:
=over 4
-=item L<Math::Prime::Util> looks in the sieve for a fast bit lookup if that
- exists (default up to 30,000 but it can be expanded, e.g.
- C<prime_precalc>), uses trial division for numbers higher than this but
- not too large (0.1M on 64-bit machines, 100M on 32-bit machines), a
- deterministic set of Miller-Rabin tests for 64-bit and smaller numbers,
- and a BPSW test for bigints.
-
-=item L<Math::Prime::XS> does trial divisions, which is wonderful if the input
- has a small factor (or is small itself). But if given a large prime it
- can take orders of magnitude longer. It does not support bigints.
-
-=item L<Math::Prime::FastSieve> only works in a sieved range, which is really
- fast if you can do it (M::P::U will do the same if you call
- C<prime_precalc>). Larger inputs just need too much time and memory
- for the sieve.
-
-=item L<Math::Primality> uses GMP for all work. Under ~32-bits it uses 2 or 3
- MR tests, while above 4759123141 it performs a BPSW test. This is is
- fantastic for bigints over 2^64, but it is significantly slower than
- native precision tests. With 64-bit numbers it is generally an order of
- magnitude or more slower than any of the others. Once bigints are being
- used, its performance is quite good. It is faster than this module unless
- L<Math::Prime::Util::GMP> has been installed, in which case this module
- is just a little bit faster.
-
-=item L<Math::Pari> has some very effective code, but it has some overhead to
- get to it from Perl. That means for small numbers it is relatively slow:
- an order of magnitude slower than M::P::XS and M::P::Util (though arguably
- this is only important for benchmarking since "slow" is ~2 microseconds).
- Large numbers transition over to smarter tests so don't slow down much.
- The C<ispseudoprime(n,0)> function will perform the BPSW test and is
- fast even for large inputs.
+=item L<Math::Prime::Util>
+
+looks in the sieve for a fast bit lookup if that exists (default up to 30,000
+but it can be expanded, e.g. C<prime_precalc>), uses trial division for
+numbers higher than this but not too large (0.1M on 64-bit machines,
+100M on 32-bit machines), a deterministic set of Miller-Rabin tests for
+64-bit and smaller numbers, and a BPSW test for bigints.
+
+=item L<Math::Prime::XS>
+
+does trial divisions, which is wonderful if the input has a small factor
+(or is small itself). But if given a large prime it can take orders of
+magnitude longer. It does not support bigints.
+
+=item L<Math::Prime::FastSieve>
+
+only works in a sieved range, which is really fast if you can do it
+(M::P::U will do the same if you call C<prime_precalc>). Larger inputs
+just need too much time and memory for the sieve.
+
+=item L<Math::Primality>
+
+uses GMP for all work. Under ~32-bits it uses 2 or 3 MR tests, while
+above 4759123141 it performs a BPSW test. This is is fantastic for
+bigints over 2^64, but it is significantly slower than native precision
+tests. With 64-bit numbers it is generally an order of magnitude or more
+slower than any of the others. Once bigints are being used, its
+performance is quite good. It is faster than this module unless
+L<Math::Prime::Util::GMP> has been installed, in which case this module
+is just a little bit faster.
+
+=item L<Math::Pari>
+
+has some very effective code, but it has some overhead to get to it from
+Perl. That means for small numbers it is relatively slow: an order of
+magnitude slower than M::P::XS and M::P::Util (though arguably this is
+only important for benchmarking since "slow" is ~2 microseconds). Large
+numbers transition over to smarter tests so don't slow down much. The
+C<ispseudoprime(n,0)> function will perform the BPSW test and is fast
+even for large inputs.
=back
@@ -3116,29 +3183,53 @@ excellent versions in the public domain).
=over 4
-=item Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.",
preprint, 2010. L<http://arxiv.org/abs/1002.0442/>
+=item *
+
+Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.",
preprint, 2010. L<http://arxiv.org/abs/1002.0442/>
+
+=item *
+
+Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres
premiers", PhD thesis, 1998. In French, but the mathematics is readable and
highly recommended reading if you're interesting in prime number bounds.
L<http://www.unilim.fr/laco/theses/1998/T1998_01.html>
+
+=item *
+
+Gabriel Mincu, "An Asymptotic Expansion", Journal of Inequalities in Pure and
Applied Mathematics, v4, n2, 2003. A very readable account of Cipolla's 1902
nth prime approximation.
L<http://www.emis.de/journals/JIPAM/images/153_02_JIPAM/153_02.pdf>
+
+=item *
+
+David M. Smith, "Multiple-Precision Exponential Integral and Related
Functions".
+
+=item *
-=item Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres
premiers", PhD thesis, 1998. In French, but the mathematics is readable and
highly recommended reading if you're interesting in prime number bounds.
L<http://www.unilim.fr/laco/theses/1998/T1998_01.html>
+Vincent Pegoraro and Philipp Slusallek, "On the Evaluation of the
Complex-Valued Exponential Integral".
-=item Gabriel Mincu, "An Asymptotic Expansion", Journal of Inequalities in
Pure and Applied Mathematics, v4, n2, 2003. A very readable account of
Cipolla's 1902 nth prime approximation.
L<http://www.emis.de/journals/JIPAM/images/153_02_JIPAM/153_02.pdf>
+=item *
-=item David M. Smith, "Multiple-Precision Exponential Integral and Related
Functions".
+William H. Press et al., "Numerical Recipes", 3rd edition.
-=item Vincent Pegoraro and Philipp Slusallek, "On the Evaluation of the
Complex-Valued Exponential Integral".
+=item *
-=item William H. Press et al., "Numerical Recipes", 3rd edition.
+W. J. Cody and Henry C. Thacher, Jr., "Rational Chevyshev Approximations for
the Exponential Integral E_1(x)".
-=item W. J. Cody and Henry C. Thacher, Jr., "Rational Chevyshev Approximations
for the Exponential Integral E_1(x)".
+=item *
-=item W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., "Chebyshev
Approximations for the Riemann Zeta Function", Mathematics of Computation, v25,
n115, pp 537-547, July 1971.
+W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., "Chebyshev
Approximations for the Riemann Zeta Function", Mathematics of Computation, v25,
n115, pp 537-547, July 1971.
-=item Ueli M. Maurer, "Fast Generation of Prime Numbers and Secure Public-Key
Cryptographic Parameters", 1995.
L<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2151>
+=item *
-=item Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number
Generation With Fewer Random Bits", 2011. L<http://eprint.iacr.org/2011/481>
+Ueli M. Maurer, "Fast Generation of Prime Numbers and Secure Public-Key
Cryptographic Parameters", 1995.
L<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2151>
-=item Douglas A. Stoll and Patrick Demichel , "The impact of ζ(s) complex
zeros on π(x) for x E<lt> 10^{10^{13}}", Mathematics of Computation, v80, n276,
pp 2381-2394, October 2011.
L<http://www.ams.org/journals/mcom/2011-80-276/S0025-5718-2011-02477-4/home.html>
+=item *
+
+Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number
Generation With Fewer Random Bits", 2011. L<http://eprint.iacr.org/2011/481>
+
+=item *
+
+Douglas A. Stoll and Patrick Demichel , "The impact of ζ(s) complex zeros on
π(x) for x E<lt> 10^{10^{13}}", Mathematics of Computation, v80, n276, pp
2381-2394, October 2011.
L<http://www.ams.org/journals/mcom/2011-80-276/S0025-5718-2011-02477-4/home.html>
+
+=item *
-=item L<OEIS: Primorial|http://oeis.org/wiki/Primorial>.
+L<OEIS: Primorial|http://oeis.org/wiki/Primorial>.
=back
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index b69b4b4..051422e 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -985,13 +985,20 @@ sub _poly_mod_mul {
for (my $ix = 0; $ix <= $px_degree; $ix++) {
my $px_at_ix = $px->[$ix];
next unless $px_at_ix;
- foreach my $iy (@indices_y) {
- my $py_at_iy = $py->[$iy];
- my $rindex = ($ix + $iy) % $r; # reduce mod X^r-1
- if (!defined $res[$rindex]) {
- $res[$rindex] = $_poly_bignum ? Math::BigInt->bzero : 0
+ if ($_poly_bignum) {
+ foreach my $iy (@indices_y) {
+ my $py_px = $py->[$iy] * $px_at_ix;
+ my $rindex = ($ix + $iy) % $r; # reduce mod X^r-1
+ $res[$rindex] = Math::BigInt->bzero unless defined $res[$rindex];
+ $res[$rindex]->badd($py_px)->bmod($n);
+ }
+ } else {
+ foreach my $iy (@indices_y) {
+ my $py_px = $py->[$iy] * $px_at_ix;
+ my $rindex = ($ix + $iy) % $r; # reduce mod X^r-1
+ $res[$rindex] = 0 unless defined $res[$rindex];
+ $res[$rindex] = ($res[$rindex] + $py_px) % $n;
}
- $res[$rindex] = ($res[$rindex] + ($py_at_iy * $px_at_ix)) % $n;
}
}
# In case we had upper terms go to zero after modulo, reduce the degree.
@@ -1024,17 +1031,15 @@ sub _test_anr {
sub is_aks_prime {
my $n = shift;
- if (ref($n) ne 'Math::BigInt') {
- if (!defined $MATH::BigInt::VERSION) {
- eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; }
- or do { croak "Cannot load Math::BigInt "; }
- }
- if (!defined $MATH::BigFloat::VERSION) {
- eval { require Math::BigFloat; Math::BigFloat->import(); 1; }
- or do { croak "Cannot load Math::BigFloat "; }
- }
- $n = Math::BigInt->new("$n");
+ if (!defined $MATH::BigInt::VERSION) {
+ eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; }
+ or do { croak "Cannot load Math::BigInt "; }
}
+ if (!defined $MATH::BigFloat::VERSION) {
+ eval { require Math::BigFloat; Math::BigFloat->import(); 1; }
+ or do { croak "Cannot load Math::BigFloat "; }
+ }
+ $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt';
return 0 if $n < 2;
return 0 if _is_perfect_power($n);
diff --git a/t/80-pp.t b/t/80-pp.t
index 94f7481..1ec86d5 100644
--- a/t/80-pp.t
+++ b/t/80-pp.t
@@ -466,7 +466,10 @@ is( is_aks_prime(65), 0, "AKS: 65 is composite (caught in
trial)" );
is( is_aks_prime(23), 1, "AKS: 23 is prime (r >= n)" );
is( is_aks_prime(101), 1, "AKS: 101 is prime (passed anr test)" );
is( is_aks_prime(70747), 0, "AKS: 70747 is composite (n mod r)" );
-is( is_aks_prime(74513), 0, "AKS: 74513 is composite (failed anr test)" );
+SKIP: {
+ skip "Skipping PP AKS test on 32-bit machine", 1 unless $use64 || $extra;
+ is( is_aks_prime(74513), 0, "AKS: 74513 is composite (failed anr test)" );
+}
###############################################################################
--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git
_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
