This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.19
in repository libmath-prime-util-perl.

commit a635e5ede543d3d84d734f3f463c21006705e9d3
Author: Dana Jacobsen <d...@acm.org>
Date:   Fri Feb 1 02:12:11 2013 -0800

    Modify validation to lower overhead
---
 Changes                        |  4 ++-
 MANIFEST                       |  2 ++
 examples/bench-mp-nextprime.pl | 28 ++++++++++++++++++++
 examples/bench-mp-psrp.pl      | 29 ++++++++++++++++++++
 lib/Math/Prime/Util.pm         | 60 ++++++++++++++++++++++++++++--------------
 lib/Math/Prime/Util/PP.pm      |  5 +++-
 6 files changed, 106 insertions(+), 22 deletions(-)

diff --git a/Changes b/Changes
index 4d678e8..6e062a8 100644
--- a/Changes
+++ b/Changes
@@ -1,6 +1,6 @@
 Revision history for Perl extension Math::Prime::Util.
 
-0.19  ?? January 2012
+0.19  ?? February 2012
 
     - Update MR bases with newest from http://miller-rabin.appspot.com/.
 
@@ -11,6 +11,8 @@ Revision history for Perl extension Math::Prime::Util.
 
     - Added a few tests to give better coverage.
 
+    - Adjust some validation tests to cut down on overhead.
+
 0.18  14 January 2012
 
     - Add random_strong_prime.
diff --git a/MANIFEST b/MANIFEST
index 2e04349..6f59e04 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -39,6 +39,8 @@ examples/bench-random-prime-bigint.pl
 examples/bench-pp-count.pl
 examples/bench-pp-isprime.pl
 examples/bench-pp-sieve.pl
+examples/bench-mp-nextprime.pl
+examples/bench-mp-psrp.pl
 examples/test-factor-yafu.pl
 examples/test-factor-mpxs.pl
 examples/test-nextprime-yafu.pl
diff --git a/examples/bench-mp-nextprime.pl b/examples/bench-mp-nextprime.pl
new file mode 100644
index 0000000..dca6555
--- /dev/null
+++ b/examples/bench-mp-nextprime.pl
@@ -0,0 +1,28 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use Math::Prime::Util;
+use Math::Prime::Util::GMP;
+use Math::Primality;
+use Benchmark qw/:all/;
+my $count = shift || -2;
+srand(29);  # So we have repeatable results
+
+test_at_digits($_, 1000) for (5, 15, 25, 50, 200);
+
+sub test_at_digits {
+  my($digits, $numbers) = @_;
+  die "Digits must be > 0" unless $digits > 0;
+
+  my $start = Math::Prime::Util::random_ndigit_prime($digits) - 3;
+  my $end = $start;
+  $end = Math::Prime::Util::GMP::next_prime($end) for 1 .. $numbers;
+
+  print "next_prime x $numbers starting at $start\n";
+
+  cmpthese($count,{
+    'MP'       => sub { my $n = $start; $n = Math::Primality::next_prime($n) 
for 1..$numbers; die "MP ended with $n instead of $end" unless $n == $end; },
+    'MPU'      => sub { my $n = $start; $n = Math::Prime::Util::next_prime($n) 
for 1..$numbers; die "MPU ended with $n instead of $end" unless $n == $end; },
+    'MPU GMP'  => sub { my $n = $start; $n = 
Math::Prime::Util::GMP::next_prime($n) for 1..$numbers; die "MPU GMP ended with 
$n instead of $end" unless $n == $end; },
+  });
+}
diff --git a/examples/bench-mp-psrp.pl b/examples/bench-mp-psrp.pl
new file mode 100644
index 0000000..337d5ae
--- /dev/null
+++ b/examples/bench-mp-psrp.pl
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use Math::Prime::Util;
+use Math::Prime::Util::GMP;
+use Math::Primality;
+use Benchmark qw/:all/;
+use List::Util qw/min max/;
+my $count = shift || -2;
+srand(29);  # So we have repeatable results
+
+test_at_digits($_, 1000) for (5, 15, 25, 50, 200);
+
+sub test_at_digits {
+  my($digits, $numbers) = @_;
+  die "Digits must be > 0" unless $digits > 0;
+
+  # We get a mix of primes and non-primes.
+  my @nums = map { Math::Prime::Util::random_ndigit_prime($digits)+2 } 1 .. 
$numbers;
+  print "is_strong_pseudoprime for $numbers random $digits-digit numbers",
+        " (", min(@nums), " - ", max(@nums), ")\n";
+
+  cmpthese($count,{
+    'MP'      =>sub {Math::Primality::is_strong_pseudoprime($_,3) for @nums;},
+    'MPU'     =>sub {Math::Prime::Util::is_strong_pseudoprime($_,3) for 
@nums;},
+    'MPU PP'  =>sub {Math::Prime::Util::PP::miller_rabin($_,3) for @nums;},
+    'MPU GMP' =>sub {Math::Prime::Util::GMP::is_strong_pseudoprime($_,3) for 
@nums;},
+  });
+}
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index cc2a033..11aa71a 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -209,24 +209,36 @@ sub prime_set_config {
   1;
 }
 
+my $_bigint_small;
 sub _validate_positive_integer {
   my($n, $min, $max) = @_;
   croak "Parameter must be defined" if !defined $n;
-  croak "Parameter '$n' must be a positive integer"
-        if ref($n) ne 'Math::BigInt' && $n =~ tr/0123456789//c;
+  if (ref($n) eq 'Math::BigInt') {
+    croak "Parameter '$n' must be a positive integer" unless $n->sign() eq '+';
+  } else {
+    croak "Parameter '$n' must be a positive integer"
+          if $n eq '' || $n =~ tr/0123456789//c;
+  }
   croak "Parameter '$n' must be >= $min" if defined $min && $n < $min;
   croak "Parameter '$n' must be <= $max" if defined $max && $n > $max;
-  # The second term is used instead of '<=' to fix strings like ~0+delta.
-  # The third works around a rare BigInt bug (e.g. 23 > 18446744073709551615 
!!)
-  if ($n < $_Config{'maxparam'} || int($n) eq $_Config{'maxparam'} || "$n" < 
$_Config{'maxparam'}) {
-    $_[0] = $_[0]->as_number() if ref($_[0]) eq 'Math::BigFloat';
-    $_[0] = int($_[0]->bstr) if ref($_[0]) eq 'Math::BigInt';
-  } elsif (ref($n) ne 'Math::BigInt') {
-    croak "Parameter '$n' outside of integer range" if !defined 
$bigint::VERSION;
-    $_[0] = Math::BigInt->new("$n"); # Make $n a proper bigint object
-    $_[0]->upgrade(undef) if $_[0]->upgrade();  # Stop BigFloat upgrade
+
+  if (ref($_[0])) {
+    $_[0] = Math::BigInt->new("$_[0]") unless ref($_[0]) eq 'Math::BigInt';
+    $_bigint_small = Math::BigInt->new("$_Config{'maxparam'}")
+                   unless defined $_bigint_small;
+    if ($_[0]->bacmp($_bigint_small) <= 0) {
+      $_[0] = int($_[0]->bstr);
+    } else {
+      $_[0]->upgrade(undef) if $_[0]->upgrade();  # Stop BigFloat upgrade
+    }
   } else {
-    $_[0]->upgrade(undef) if $_[0]->upgrade();  # Stop BigFloat upgrade
+    # The second term is used instead of '<=' to fix strings like ~0+delta.
+    if ( ! ($n < $_Config{'maxparam'} || int($n) eq $_Config{'maxparam'}) ) {
+      # We were handed a string representing a big number.
+      croak "Parameter '$n' outside of integer range" if !defined 
$bigint::VERSION;
+      $_[0] = Math::BigInt->new("$n"); # Make $n a proper bigint object
+      $_[0]->upgrade(undef) if $_[0]->upgrade();  # Stop BigFloat upgrade
+    }
   }
   # One of these will be true:
   #     1) $n <= max and $n is not a bigint
@@ -554,7 +566,7 @@ sub primes {
     }
 
     $low-- if $low == 2;  # Low of 2 becomes 1 for our program.
-    croak "Invalid _random_prime parameters" if ($low % 2) == 0 || ($high % 2) 
== 0;
+    confess "Invalid _random_prime parameters: $low, $high" if ($low % 2) == 0 
|| ($high % 2) == 0;
 
     # We're going to look at the odd numbers only.
     #my $range = $high - $low + 1;
@@ -1204,7 +1216,7 @@ sub is_prime {
   return 0 if defined $n && $n < 2;
   _validate_positive_integer($n);
 
-  return _XS_is_prime($n) if $n <= $_XS_MAXVAL;
+  return _XS_is_prime($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL;
   return Math::Prime::Util::GMP::is_prime($n) if $_HAVE_GMP;
   return is_prob_prime($n);
 }
@@ -1226,7 +1238,7 @@ sub next_prime {
   _validate_positive_integer($n);
 
   # If we have XS and n is either small or bigint is unknown, then use XS.
-  return _XS_next_prime($n) if $n <= $_XS_MAXVAL
+  return _XS_next_prime($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL
              && (!defined $bigint::VERSION || $n < $_Config{'maxprime'} );
 
   # Try to stick to the plan with respect to maximum return values.
@@ -1245,7 +1257,7 @@ sub prev_prime {
   my($n) = @_;
   _validate_positive_integer($n);
 
-  return _XS_prev_prime($n) if $n <= $_XS_MAXVAL;
+  return _XS_prev_prime($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL;
   if ($_HAVE_GMP) {
     # If $n is a bigint object, try to make the return value the same
     return (ref($n) eq 'Math::BigInt')
@@ -1302,7 +1314,7 @@ sub factor {
   my($n) = @_;
   _validate_positive_integer($n);
 
-  return _XS_factor($n) if $n <= $_XS_MAXVAL;
+  return _XS_factor($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL;
 
   if ($_HAVE_GMP) {
     my @factors = Math::Prime::Util::GMP::factor($n);
@@ -1319,7 +1331,7 @@ sub is_strong_pseudoprime {
   my($n) = shift;
   _validate_positive_integer($n);
   # validate bases?
-  return _XS_miller_rabin($n, @_) if $n <= $_XS_MAXVAL;
+  return _XS_miller_rabin($n, @_) if ref($n) ne 'Math::BigInt' && $n <= 
$_XS_MAXVAL;
   return Math::Prime::Util::GMP::is_strong_pseudoprime($n, @_) if $_HAVE_GMP;
   return Math::Prime::Util::PP::miller_rabin($n, @_);
 }
@@ -1365,7 +1377,7 @@ sub is_prob_prime {
   return 0 if defined $n && $n < 2;
   _validate_positive_integer($n);
 
-  return _XS_is_prob_prime($n) if $n <= $_XS_MAXVAL;
+  return _XS_is_prob_prime($n) if ref($n) ne 'Math::BigInt' && $n <= 
$_XS_MAXVAL;
   return Math::Prime::Util::GMP::is_prob_prime($n) if $_HAVE_GMP;
 
   return 2 if $n == 2 || $n == 3 || $n == 5 || $n == 7;
@@ -1407,7 +1419,7 @@ sub is_provable_prime {
   _validate_positive_integer($n);
 
   # Shortcut some of the calls.
-  return _XS_is_prime($n) if $n <= $_XS_MAXVAL;
+  return _XS_is_prime($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL;
   return Math::Prime::Util::GMP::is_provable_prime($n) if $_HAVE_GMP
                        && defined &Math::Prime::Util::GMP::is_provable_prime;
 
@@ -2903,6 +2915,14 @@ 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:
+
+  use Math::Prime::Util qw/primes/;
+  my $sum = 0;
+  $sum += $_ for @{primes(2_000_000)};
+  say $sum;
+
+
 =head1 LIMITATIONS
 
 I have not completed testing all the functions near the word size limit
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index b17689c..b69b4b4 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -879,7 +879,10 @@ sub is_strong_lucas_pseudoprime {
   # It's now time to perform the Lucas pseudoprimality test using $D.
 
   if (ref($n) ne 'Math::BigInt') {
-    require 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 "; }
+    }
     $n = Math::BigInt->new("$n");
   }
 

-- 
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

Reply via email to