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

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

commit c4219ab04d0c6e57b57539c0017478a4b33b4344
Author: Dana Jacobsen <d...@acm.org>
Date:   Sun Jul 8 05:09:37 2012 -0600

    More random prime changes
---
 XS.xs                     |  4 ++--
 lib/Math/Prime/Util.pm    | 37 ++++++++++++++++++++++++++++++-------
 lib/Math/Prime/Util/PP.pm | 44 ++++++++++++++++++++++----------------------
 3 files changed, 54 insertions(+), 31 deletions(-)

diff --git a/XS.xs b/XS.xs
index 2821618..54937c0 100644
--- a/XS.xs
+++ b/XS.xs
@@ -307,9 +307,9 @@ _XS_factor(IN UV n)
     }
 
 void
-trial_factor(IN UV n)
+trial_factor(IN UV n, IN UV maxfactor = 0)
   PPCODE:
-    SIMPLE_FACTOR(trial_factor, n, UV_MAX);
+    SIMPLE_FACTOR(trial_factor, n, maxfactor);
 
 void
 fermat_factor(IN UV n, IN UV maxrounds = 64*1024*1024)
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 21daaf7..cccd6bb 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -327,6 +327,26 @@ sub primes {
   # Returns a uniform number between [0,$range] inclusive.
   my $get_rand_range = sub {
     my($range) = @_;
+    my $rbits = 0;
+    if (ref($range) eq 'Math::BigInt') {
+      $rbits = length($range->as_bin) - 2;
+    } else {
+      my $t = $range - 1;
+      while ($t) { $rbits++; $t >>= 1; }
+    }
+    while (1) {
+      my $rbitsleft = $rbits;
+      my $U = $range - $range;   # zero in possible bigint
+      while ($rbitsleft > 0) {
+        my $usebits = ($rbitsleft > $rand_max_bits) ? $rand_max_bits : 
$rbitsleft;
+        $U = ($U << $usebits) + $irandf->(1 << $usebits);
+        $rbitsleft -= $usebits;
+      }
+      return $U if $U <= $range;
+    }
+  };
+  my $get_rand_range2 = sub {
+    my($range) = @_;
     my $max = int($range) + 1;
     my $offset = 0;
     while ($max > 1) {
@@ -539,7 +559,7 @@ sub primes {
     my $I = Math::BigInt->new(2)->bpow($k-1)->bdiv(2 * $q)->bfloor;
     #warn "I = $I\n";
 
-    my @primes = @{primes($B)};
+    my @primes = @{primes(11,$B)};
 
     while (1) {
       # R is a random number between $I+1 and 2*$I
@@ -548,9 +568,12 @@ sub primes {
       # We constructed a promising looking $n.  Now test it.
 
       # Trial divide up to $B
+      next if !($n % 3);
+      next if !($n % 5);
+      next if !($n % 7);
       my $looks_prime = 1;
       foreach my $p (@primes) {
-        do { $looks_prime = 0; last; } if ($n % $p) == 0;
+        do { $looks_prime = 0; last; } if !($n % $p);
       }
       next unless $looks_prime;
       #warn "$n passes trial division\n";
@@ -581,10 +604,10 @@ sub primes {
       #   next if $z is a perfect square
       # Menezes seems to imply only the q test needs to be done.
 
-      # Finally, verify with a BPSW test on the result.  This will either,
+      # We perhaps could verify with a BPSW test on the result.  This could:
       #  1) save us from accidently outputing a non-prime due to some mistake
       #  2) make history by finding the first known BPSW pseudo-prime
-      croak "Maurer prime $n failed BPSW" unless is_prob_prime($n);
+      # croak "Maurer prime $n failed BPSW" unless is_prob_prime($n);
       #warn "     and passed BPSW.\n";
 
       return $n;
@@ -634,7 +657,7 @@ sub moebius {
   return 1 if $n == 1;
 
   # Quick check for small replicated factors
-  return 0 if ($n >= 25) && (($n % 4) == 0 || ($n % 9) == 0 || ($n % 25) == 0);
+  return 0 if ($n >= 25) && (!($n % 4) || !($n % 9) || !($n % 25));
 
   my @factors = factor($n);
   my %all_factors;
@@ -808,9 +831,9 @@ sub is_prob_prime {
 
   return 2 if $n == 2 || $n == 3 || $n == 5 || $n == 7;
   return 0 if $n < 11;
-  return 0 if ($n % 2) == 0 || ($n % 3) == 0 || ($n % 5) == 0 || ($n % 7) == 0;
+  return 0 if !($n % 2) || !($n % 3) || !($n % 5) || !($n % 7);
   foreach my $i (qw/11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71/) {
-    return 2 if $i*$i > $n;   return 0 if ($n % $i) == 0;
+    return 2 if $i*$i > $n;   return 0 if !($n % $i);
   }
 
   if ($n < 105936894253) {   # BPSW seems to be faster after this
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index 525bcb3..72bb812 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -98,7 +98,7 @@ sub _is_prime7 {  # n must not be divisible by 2, 3, or 5
 
   foreach my $i (qw/7 11 13 17 19 23 29/) {
     return 2 if $i*$i > $n;
-    return 0 if ($n % $i) == 0;
+    return 0 if !($n % $i);
   }
 
   return Math::Prime::Util::is_prob_prime($n) if $n > 10_000_000;
@@ -106,24 +106,24 @@ sub _is_prime7 {  # n must not be divisible by 2, 3, or 5
   my $limit = int(sqrt($n));
   my $i = 31;
   while (($i+30) <= $limit) {
-    return 0 if ($n % $i) == 0;  $i += 6;
-    return 0 if ($n % $i) == 0;  $i += 4;
-    return 0 if ($n % $i) == 0;  $i += 2;
-    return 0 if ($n % $i) == 0;  $i += 4;
-    return 0 if ($n % $i) == 0;  $i += 2;
-    return 0 if ($n % $i) == 0;  $i += 4;
-    return 0 if ($n % $i) == 0;  $i += 6;
-    return 0 if ($n % $i) == 0;  $i += 2;
+    return 0 if !($n % $i);  $i += 6;
+    return 0 if !($n % $i);  $i += 4;
+    return 0 if !($n % $i);  $i += 2;
+    return 0 if !($n % $i);  $i += 4;
+    return 0 if !($n % $i);  $i += 2;
+    return 0 if !($n % $i);  $i += 4;
+    return 0 if !($n % $i);  $i += 6;
+    return 0 if !($n % $i);  $i += 2;
   }
   while (1) {
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 6;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 4;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 2;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 4;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 2;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 4;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 6;
-    last if $i > $limit;  return 0 if ($n % $i) == 0;  $i += 2;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 6;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 4;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 2;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 4;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 2;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 4;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 6;
+    last if $i > $limit;  return 0 if !($n % $i);  $i += 2;
   }
   2;
 }
@@ -135,7 +135,7 @@ sub is_prime {
   return 2 if ($n == 2) || ($n == 3) || ($n == 5);  # 2, 3, 5 are prime
   return 0 if $n < 7;             # everything else below 7 is composite
                                   # multiples of 2,3,5 are composite
-  return 0 if (($n % 2) == 0) || (($n % 3) == 0) || (($n % 5) == 0);
+  return 0 if !($n % 2) || !($n % 3) || !($n % 5);
   return _is_prime7($n);
 }
 
@@ -530,7 +530,7 @@ sub miller_rabin {
 
   return 0 if ($n == 0) || ($n == 1);
   return 1 if ($n == 2) || ($n == 3);
-  return 0 if ($n % 2) == 0;
+  return 0 if !($n % 2);
 
   if ( ref($n) eq 'Math::BigInt' ) {
 
@@ -777,9 +777,9 @@ sub _basic_factor {
   return ($_[0]) if $_[0] < 4;
 
   my @factors;
-  while ( ($_[0] % 2) == 0 ) { push @factors, 2;  $_[0] = int($_[0] / 2); }
-  while ( ($_[0] % 3) == 0 ) { push @factors, 3;  $_[0] = int($_[0] / 3); }
-  while ( ($_[0] % 5) == 0 ) { push @factors, 5;  $_[0] = int($_[0] / 5); }
+  while ( !($_[0] % 2) ) { push @factors, 2;  $_[0] = int($_[0] / 2); }
+  while ( !($_[0] % 3) ) { push @factors, 3;  $_[0] = int($_[0] / 3); }
+  while ( !($_[0] % 5) ) { push @factors, 5;  $_[0] = int($_[0] / 5); }
 
   # Stop using bignum if we can
   $_[0] = int($_[0]->bstr) if ref($_[0]) eq 'Math::BigInt' && $_[0] <= ~0;

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