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

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

commit 4a10314df4a3133659515da23ca42baf0187290b
Author: Dana Jacobsen <d...@acm.org>
Date:   Tue Dec 31 16:24:33 2013 -0800

    Move factor_exp and divisors to XS->Perl, merge with factor
---
 XS.xs                  |  89 +++++++++++++++++++++-------------------
 factor.c               |  25 ++++++++----
 lib/Math/Prime/Util.pm | 109 +++++++++++++++++--------------------------------
 3 files changed, 100 insertions(+), 123 deletions(-)

diff --git a/XS.xs b/XS.xs
index 4c29062..23a5fe2 100644
--- a/XS.xs
+++ b/XS.xs
@@ -278,41 +278,6 @@ sieve_primes(IN UV low, IN UV high)
     RETVAL
 
 void
-_XS_factor_exp(IN UV n)
-  PREINIT:
-    UV factors[MPU_MAX_FACTORS+1];
-    UV exponents[MPU_MAX_FACTORS+1];
-    int i, nfactors;
-  PPCODE:
-    nfactors = factor_exp(n, factors, exponents);
-    if (GIMME_V == G_SCALAR) {
-      PUSHs(sv_2mortal(newSVuv(nfactors)));
-    } else {
-      /* Return ( [p1,e1], [p2,e2], [p3,e3], ... ) */
-      if (n == 1)  XSRETURN_EMPTY;
-      EXTEND(SP, nfactors);
-      for (i = 0; i < nfactors; i++) {
-        AV* av = newAV();
-        av_push(av, newSVuv(factors[i]));
-        av_push(av, newSVuv(exponents[i]));
-        PUSHs( sv_2mortal(newRV_noinc( (SV*) av )) );
-      }
-    }
-
-void
-_XS_divisors(IN UV n)
-  PPCODE:
-    if (GIMME_V == G_SCALAR) {
-      PUSHs(sv_2mortal(newSVuv( divisor_sum(n, 0) )));
-    } else {
-      UV i, ndivisors;
-      UV* divs = _divisor_list(n, &ndivisors);
-      for (i = 0; i < ndivisors; i++)
-        XPUSHs(sv_2mortal(newSVuv(divs[i])));
-      Safefree(divs);
-    }
-
-void
 trial_factor(IN UV n, ...)
   ALIAS:
     fermat_factor = 1
@@ -478,26 +443,64 @@ next_prime(IN SV* svn)
 
 void
 factor(IN SV* svn)
+  ALIAS:
+    factor_exp = 1
+    divisors = 2
+  PREINIT:
+    U32 gimme_v;
+    int status, i, nfactors;
   PPCODE:
-    U32 gimme_v =  GIMME_V;
-    int status = _validate_int(aTHX_ svn, 0);
+    gimme_v = GIMME_V;
+    status = _validate_int(aTHX_ svn, 0);
     if (status == 1) {
       UV factors[MPU_MAX_FACTORS+1];
+      UV exponents[MPU_MAX_FACTORS+1];
       UV n = my_svuv(svn);
-      int i, nfactors = factor(n, factors);
       if (gimme_v == G_SCALAR) {
-        PUSHs(sv_2mortal(newSVuv(nfactors)));
+        switch (ix) {
+          case 0:  nfactors = factor(n, factors);        break;
+          case 1:  nfactors = factor_exp(n, factors, 0); break;
+          default: nfactors = divisor_sum(n, 0);         break;
+        }
+        PUSHs(sv_2mortal(newSVuv( nfactors )));
       } else if (gimme_v == G_ARRAY) {
-        EXTEND(SP, nfactors);
-        for (i = 0; i < nfactors; i++) {
-          PUSHs(sv_2mortal(newSVuv( factors[i] )));
+        switch (ix) {
+          case 0:  nfactors = factor(n, factors);
+                   EXTEND(SP, nfactors);
+                   for (i = 0; i < nfactors; i++)
+                     PUSHs(sv_2mortal(newSVuv( factors[i] )));
+                   break;
+          case 1:  nfactors = factor_exp(n, factors, exponents);
+                   /* if (n == 1)  XSRETURN_EMPTY; */
+                   EXTEND(SP, nfactors);
+                   for (i = 0; i < nfactors; i++) {
+                     AV* av = newAV();
+                     av_push(av, newSVuv(factors[i]));
+                     av_push(av, newSVuv(exponents[i]));
+                     PUSHs( sv_2mortal(newRV_noinc( (SV*) av )) );
+                   }
+                   break;
+          default: {
+                     UV ndivisors;
+                     UV* divs = _divisor_list(n, &ndivisors);
+                     EXTEND(SP, ndivisors);
+                     for (i = 0; i < ndivisors; i++)
+                       PUSHs(sv_2mortal(newSVuv( divs[i] )));
+                     Safefree(divs);
+                   }
+                   break;
         }
       }
     } else {
-      _vcallsubn(aTHX_ gimme_v, "_generic_factor", 1);
+      switch (ix) {
+        case 0:  _vcallsubn(aTHX_ gimme_v, "_generic_factor", 1);     break;
+        case 1:  _vcallsubn(aTHX_ gimme_v, "_generic_factor_exp", 1); break;
+        default: _vcallsubn(aTHX_ gimme_v, "_generic_divisors", 1);   break;
+      }
       return; /* skip implicit PUTBACK */
     }
 
+
 void
 divisor_sum(IN SV* svn, ...)
   PPCODE:
diff --git a/factor.c b/factor.c
index 9a671c6..4b0f976 100644
--- a/factor.c
+++ b/factor.c
@@ -134,16 +134,25 @@ int factor(UV n, UV *factors)
 
 int factor_exp(UV n, UV *factors, UV* exponents)
 {
-  int i, j, nfactors = factor(n, factors);
+  int i, j, nfactors;
 
   if (n == 1) return 0;
-  exponents[0] = 1;
-  for (i = 1, j = 1; i < nfactors; i++) {
-    if (factors[i] != factors[i-1]) {
-      exponents[j] = 1;
-      factors[j++] = factors[i];
-    } else {
-      exponents[j-1]++;
+  /* MPUassert(factors != 0, "factors array is null"); */
+  nfactors = factor(n, factors);
+
+  if (exponents == 0) {
+    for (i = 1, j = 1; i < nfactors; i++)
+      if (factors[i] != factors[i-1])
+        factors[j++] = factors[i];
+  } else {
+    exponents[0] = 1;
+    for (i = 1, j = 1; i < nfactors; i++) {
+      if (factors[i] != factors[i-1]) {
+        exponents[j] = 1;
+        factors[j++] = factors[i];
+      } else {
+        exponents[j-1]++;
+      }
     }
   }
   return j;
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index fd63fc0..de9155f 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -60,8 +60,6 @@ sub import {
 sub _import_nobigint {
   $_Config{'nobigint'} = 1;
   return unless $_Config{'xs'};
-  undef *factor_exp;      *factor_exp        = \&_XS_factor_exp;
-  undef *divisors;        *divisors          = \&_XS_divisors;
  #undef *prime_count;     *prime_count       = \&_XS_prime_count;
   undef *nth_prime;       *nth_prime         = \&_XS_nth_prime;
   undef *is_pseudoprime;  *is_pseudoprime    = \&_XS_is_pseudoprime;
@@ -110,6 +108,8 @@ BEGIN {
     *znorder       = \&Math::Prime::Util::_generic_znorder;
     *znprimroot    = \&Math::Prime::Util::_generic_znprimroot;
     *factor        = \&Math::Prime::Util::_generic_factor;
+    *factor_exp    = \&Math::Prime::Util::_generic_factor_exp;
+    *divisors      = \&Math::Prime::Util::_generic_divisors;
     *forprimes     = sub (&$;$) { _generic_forprimes(@_); }; ## no critic 
qw(ProhibitSubroutinePrototypes)
     *fordivisors   = sub (&$) { _generic_fordivisors(@_); }; ## no critic 
qw(ProhibitSubroutinePrototypes)
     *forcomposites = sub (&$) { _generic_forcomposites(@_); }; ## no critic 
qw(ProhibitSubroutinePrototypes)
@@ -130,6 +130,10 @@ BEGIN {
     *pplus1_factor  = \&Math::Prime::Util::PP::pminus1_factor;   # TODO: 
implement PP p+1.
   };
 
+  # aliases for deprecated names.  Will eventually be removed.
+  *all_factors = \&divisors;
+  *miller_rabin = \&is_strong_pseudoprime;
+
   $_Config{'nobigint'} = 0;
   $_Config{'gmp'} = 0;
   # See if they have the GMP module and haven't requested it not to be used.
@@ -1231,37 +1235,6 @@ sub consecutive_integer_lcm {
   return $pn;
 }
 
-sub divisors {
-  my $n = shift;
-
-  _validate_num($n) || _validate_positive_integer($n);
-
-  return _XS_divisors($n) if $n <= $_XS_MAXVAL;
-
-  # In scalar context, returns sigma_0(n).  Very fast.
-  return divisor_sum($n,0) unless wantarray;
-  return ($n == 0) ? (0,1) : (1)  if $n <= 1;
-
-  my %all_factors;
-  foreach my $f1 (factor($n)) {
-    next if $f1 >= $n;
-    my $big_f1 = Math::BigInt->new("$f1");
-    my @to_add = map { ($_ <= ~0) ? int($_->bstr) : $_ }
-                 grep { $_ < $n }
-                 map { $big_f1 * $_ }
-                 keys %all_factors;
-    undef @all_factors{ $f1, @to_add };
-  }
-  # Add 1 and n
-  undef $all_factors{1};
-  undef $all_factors{$n};
-  my @divisors = sort {$a<=>$b} keys %all_factors;
-  return @divisors;
-}
-
-# alias the old "all_factors" to the new name: divisors
-*all_factors = \&divisors;
-
 # A008683 Moebius function mu(n)
 # A030059, A013929, A030229, A002321, A005117, A013929 all relate.
 sub _generic_moebius {
@@ -1326,7 +1299,7 @@ sub jordan_totient {
   _validate_num($n) || _validate_positive_integer($n);
   return 1 if $n <= 1;
 
-  my @pe = ($n <= $_XS_MAXVAL) ? _XS_factor_exp($n) : factor_exp($n);
+  my @pe = factor_exp($n);
 
   my $totient = $n - $n + 1;
 
@@ -1394,7 +1367,7 @@ sub _generic_forcomposites(&$;$) { ## no critic 
qw(ProhibitSubroutinePrototypes)
 sub _generic_fordivisors (&$) {    ## no critic 
qw(ProhibitSubroutinePrototypes)
   my($sub, $n) = @_;
   _validate_num($n) || _validate_positive_integer($n);
-  my @divisors = ($n <= $_XS_MAXVAL) ? _XS_divisors($n) : divisors($n);
+  my @divisors = divisors($n);
   {
     my $pp;
     local *_ = \$pp;
@@ -1436,7 +1409,7 @@ sub _generic_exp_mangoldt {
   return 2 if ($n & ($n-1)) == 0;     # n power of 2
   return 1 unless $n & 1;             # even n can't be p^m
 
-  my @pe = ($n <= $_XS_MAXVAL) ? _XS_factor_exp($n) : factor_exp($n);
+  my @pe = factor_exp($n);
   return 1 if scalar @pe > 1;
   return $pe[0]->[0];
 }
@@ -1510,7 +1483,7 @@ sub _generic_carmichael_lambda {
   # lambda(n) = phi(n)/2 for powers of two greater than 4
   return euler_phi($n)/2 if ($n & ($n-1)) == 0;
 
-  my @pe = ($n <= $_XS_MAXVAL) ? _XS_factor_exp($n) : factor_exp($n);
+  my @pe = factor_exp($n);
   $pe[0]->[1]-- if $pe[0]->[0] == 2 && $pe[0]->[1] > 2;
 
   my $lcm = Math::BigInt::blcm(
@@ -1539,7 +1512,7 @@ sub _generic_znorder {
 
   # This is easy and usually fast, but can bog down with too many divisors.
   if ($lambda <= $_XS_MAXVAL) {
-    foreach my $k (_XS_divisors($lambda)) {
+    foreach my $k (divisors($lambda)) {
       return $k if $a->copy->bmodpow("$k", $n)->is_one;
     }
     return;
@@ -1738,8 +1711,6 @@ sub _generic_factor {
   my($n) = @_;
   _validate_num($n) || _validate_positive_integer($n);
 
-  return _XS_factor($n) if $n <= $_XS_MAXVAL;
-
   if ($_HAVE_GMP) {
     my @factors;
     if ($n != 1) {
@@ -1754,42 +1725,41 @@ sub _generic_factor {
   return Math::Prime::Util::PP::factor($n);
 }
 
-sub factor_exp {
+sub _generic_factor_exp {
   my($n) = @_;
   _validate_num($n) || _validate_positive_integer($n);
 
-  return _XS_factor_exp($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL;
-
   my %exponents;
   my @factors = grep { !$exponents{$_}++ } factor($n);
   return scalar @factors unless wantarray;
   return (map { [$_, $exponents{$_}] } @factors);
 }
 
-#sub trial_factor {
-#  my($n, $limit) = @_;
-#  _validate_num($n) || _validate_positive_integer($n);
-#  $limit = 2147483647 unless defined $limit;
-#  _validate_num($limit) || _validate_positive_integer($limit);
-#  return _XS_trial_factor($n, $limit) if $n <= $_XS_MAXVAL;
-#  if ($_HAVE_GMP) {
-#    my @factors;
-#    while (1) {
-#      last if $n <= 1 || is_prob_prime($n);
-#      my @f = sort { $a <=> $b }
-#              Math::Prime::Util::GMP::trial_factor($n, $limit);
-#      pop(@f);  # Remove remainder
-#      last unless scalar @f > 0;
-#      foreach my $f (@f) {
-#        push @factors, $f;
-#        $n /= $f;
-#      }
-#    }
-#    push @factors, $n if $n > 1;
-#    return @factors;
-#  }
-#  return Math::Prime::Util::PP::trial_factor($n, $limit);
-#}
+sub _generic_divisors {
+  my($n) = @_;
+  _validate_num($n) || _validate_positive_integer($n);
+
+  # In scalar context, returns sigma_0(n).  Very fast.
+  return divisor_sum($n,0) unless wantarray;
+  return ($n == 0) ? (0,1) : (1)  if $n <= 1;
+
+  my %all_factors;
+  foreach my $f1 (factor($n)) {
+    next if $f1 >= $n;
+    my $big_f1 = Math::BigInt->new("$f1");
+    my @to_add = map { ($_ <= ~0) ? int($_->bstr) : $_ }
+                 grep { $_ < $n }
+                 map { $big_f1 * $_ }
+                 keys %all_factors;
+    undef @all_factors{ $f1, @to_add };
+  }
+  # Add 1 and n
+  undef $all_factors{1};
+  undef $all_factors{$n};
+  my @divisors = sort {$a<=>$b} keys %all_factors;
+  return @divisors;
+}
+
 
 sub is_pseudoprime {
   my($n, $a) = @_;
@@ -1871,11 +1841,6 @@ sub is_frobenius_underwood_pseudoprime {
   return Math::Prime::Util::PP::is_frobenius_underwood_pseudoprime($n);
 }
 
-sub miller_rabin {
-  #warn "miller_rabin() is deprecated. Use is_strong_pseudoprime instead.";
-  return is_strong_pseudoprime(@_);
-}
-
 sub lucas_sequence {
   my($n, $P, $Q, $k) = @_;
   _validate_num($n) || _validate_positive_integer($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