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 0846451f18a184d86d369695a1cf201608eea872
Author: Dana Jacobsen <d...@acm.org>
Date:   Thu Jan 2 12:33:00 2014 -0800

    Move prime_count, nth_prime to XS
---
 XS.xs                  | 132 ++++++++++++++++++++++++++++---------------------
 lib/Math/Prime/Util.pm |  61 ++++++-----------------
 t/13-primecount.t      |   2 +-
 3 files changed, 91 insertions(+), 104 deletions(-)

diff --git a/XS.xs b/XS.xs
index 87547e4..ff3dbe0 100644
--- a/XS.xs
+++ b/XS.xs
@@ -76,13 +76,18 @@
   static const unsigned int ivmax_maxlen = 10;
   static const char uvmax_str[] = "4294967295";
   static const char ivmax_str[] = "2147483648";
+  static const UV _max_prime    = UVCONST(4294967291);
+  static const UV _max_primeidx = UVCONST(203280221);
 #else
   static const unsigned int uvmax_maxlen = 20;
   static const unsigned int ivmax_maxlen = 19;
   static const char uvmax_str[] = "18446744073709551615";
   static const char ivmax_str[] =  "9223372036854775808";
+  static const UV _max_prime    = UVCONST(18446744073709551557);
+  static const UV _max_primeidx = UVCONST(425656284035217743);
 #endif
 
+
 /* Is this a pedantically valid integer?
  * Croaks if undefined or invalid.
  * Returns 0 if it is an object or a string too large for a UV.
@@ -159,12 +164,6 @@ static int _vcallsubn(pTHX_ I32 flags, const char* name, 
int nargs)
 }
 #define _vcallsub(func) (void)_vcallsubn(aTHX_ G_SCALAR, func, 1)
 
-#if BITS_PER_WORD == 64
-static const UV _max_prime = UVCONST(18446744073709551557);
-#else
-static const UV _max_prime = UVCONST(4294967291);
-#endif
-
 
 MODULE = Math::Prime::Util     PACKAGE = Math::Prime::Util
 
@@ -213,40 +212,54 @@ prime_precalc(IN UV n)
     return; /* skip implicit PUTBACK */
 
 void
-_XS_prime_count(IN UV low, IN UV high = 0)
+prime_count(IN SV* svlo, ...)
+  ALIAS:
+    _XS_segment_pi = 1
+  PREINIT:
+    int lostatus, histatus;
+    UV lo, hi;
   PPCODE:
-    if (high == 0) {   /* Without a Perl layer in front of this, we'll have */
-      high = low;      /* the pathological case of a-0 turning into 0-a.    */
-      low = 0;
-    }
-    if (GIMME_V == G_VOID) {
-      prime_precalc(high);
-    } else {
-      PUSHs(sv_2mortal(newSVuv( _XS_prime_count(low, high) )));
+    lostatus = _validate_int(aTHX_ svlo, 0);
+    histatus = (items == 1 || _validate_int(aTHX_ ST(1), 0));
+    if (lostatus == 1 && histatus == 1) {
+      UV count = 0;
+      if (items == 1) {
+        lo = 2;
+        hi = my_svuv(svlo);
+      } else {
+        lo = my_svuv(svlo);
+        hi = my_svuv(ST(1));
+      }
+      if (lo <= hi) {
+        if (ix == 1 || (hi / (hi-lo+1)) > 100) {
+          count = _XS_prime_count(lo, hi);
+        } else {
+          count = _XS_LMO_pi(hi);
+          if (lo > 2)
+            count -= _XS_LMO_pi(lo-1);
+        }
+      }
+      XSRETURN_UV(count);
     }
+    _vcallsubn(aTHX_ GIMME_V, "_generic_prime_count", items);
+    return; /* skip implicit PUTBACK */
 
 UV
-_XS_nth_prime(IN UV n)
+_XS_LMO_pi(IN UV n)
   ALIAS:
-    _XS_next_prime = 1
-    _XS_prev_prime = 2
-    _XS_legendre_pi = 3
-    _XS_meissel_pi = 4
-    _XS_lehmer_pi = 5
-    _XS_LMOS_pi = 6
-    _XS_LMO_pi = 7
+    _XS_legendre_pi = 1
+    _XS_meissel_pi = 2
+    _XS_lehmer_pi = 3
+    _XS_LMOS_pi = 4
   PREINIT:
     UV ret;
   CODE:
     switch (ix) {
-      case 0: ret = _XS_nth_prime(n); break;
-      case 1: ret = _XS_next_prime(n); break;
-      case 2: ret = _XS_prev_prime(n); break;
-      case 3: ret = _XS_legendre_pi(n); break;
-      case 4: ret = _XS_meissel_pi(n); break;
-      case 5: ret = _XS_lehmer_pi(n); break;
-      case 6: ret = _XS_LMOS_pi(n); break;
-      default:ret = _XS_LMO_pi(n); break;
+      case 0: ret = _XS_LMO_pi(n); break;
+      case 1: ret = _XS_legendre_pi(n); break;
+      case 2: ret = _XS_meissel_pi(n); break;
+      case 3: ret = _XS_lehmer_pi(n); break;
+      default:ret = _XS_LMOS_pi(n); break;
     }
     RETVAL = ret;
   OUTPUT:
@@ -388,31 +401,27 @@ _XS_lucas_sequence(IN UV n, IN IV P, IN IV Q, IN UV k)
     PUSHs(sv_2mortal(newSVuv( Qk )));
 
 int
-_XS_is_prime(IN UV n, ...)
+_XS_is_lucas_pseudoprime(IN UV n, ...)
   ALIAS:
-    _XS_is_prob_prime = 1
-    _XS_is_lucas_pseudoprime = 2
-    _XS_is_strong_lucas_pseudoprime = 3
-    _XS_is_extra_strong_lucas_pseudoprime = 4
-    _XS_is_frobenius_underwood_pseudoprime = 5
-    _XS_is_almost_extra_strong_lucas_pseudoprime = 6
-    _XS_is_pseudoprime = 7
-    _XS_is_aks_prime = 8
-    _XS_BPSW = 9
+    _XS_is_strong_lucas_pseudoprime = 1
+    _XS_is_extra_strong_lucas_pseudoprime = 2
+    _XS_is_frobenius_underwood_pseudoprime = 3
+    _XS_is_almost_extra_strong_lucas_pseudoprime = 4
+    _XS_is_pseudoprime = 5
+    _XS_is_aks_prime = 6
+    _XS_BPSW = 7
   PREINIT:
     int ret;
   CODE:
     switch (ix) {
-      case 0: ret = _XS_is_prime(n); break;
-      case 1: ret = _XS_is_prob_prime(n); break;
-      case 2: ret = _XS_is_lucas_pseudoprime(n, 0); break;
-      case 3: ret = _XS_is_lucas_pseudoprime(n, 1); break;
-      case 4: ret = _XS_is_lucas_pseudoprime(n, 2); break;
-      case 5: ret = _XS_is_frobenius_underwood_pseudoprime(n); break;
-      case 6: ret = _XS_is_almost_extra_strong_lucas_pseudoprime
+      case 0: ret = _XS_is_lucas_pseudoprime(n, 0); break;
+      case 1: ret = _XS_is_lucas_pseudoprime(n, 1); break;
+      case 2: ret = _XS_is_lucas_pseudoprime(n, 2); break;
+      case 3: ret = _XS_is_frobenius_underwood_pseudoprime(n); break;
+      case 4: ret = _XS_is_almost_extra_strong_lucas_pseudoprime
                     ( n, (items == 1) ? 1 : my_svuv(ST(1)) );  break;
-      case 7: ret = _XS_is_pseudoprime(n, my_svuv(ST(1)));     break;
-      case 8: ret = _XS_is_aks_prime(n); break;
+      case 5: ret = _XS_is_pseudoprime(n, my_svuv(ST(1)));     break;
+      case 6: ret = _XS_is_aks_prime(n); break;
       default:ret = _XS_BPSW(n); break;
     }
     RETVAL = ret;
@@ -449,18 +458,29 @@ void
 next_prime(IN SV* svn)
   ALIAS:
     prev_prime = 1
+    nth_prime = 2
   PPCODE:
     if (_validate_int(aTHX_ svn, 0)) {
       UV n = my_svuv(svn);
-      if (ix) {
-        XSRETURN_UV( (n < 3) ? 0 : _XS_prev_prime(n));
+      if ( ((ix == 0) && (n >= _max_prime))    ||
+           ((ix == 2) && (n >= _max_primeidx)) ) {
+        /* Out of range.  Fall through to Perl. */
       } else {
-        if (n < _max_prime)
-          XSRETURN_UV(_XS_next_prime(n));
+        UV ret;
+        switch (ix) {
+          case 0: ret = _XS_next_prime(n);  break;
+          case 1: ret = (n < 3) ? 0 : _XS_prev_prime(n);  break;
+          case 2:
+          default:ret = _XS_nth_prime(n);  break;
+        }
+        XSRETURN_UV(ret);
       }
     }
-    _vcallsub((ix == 0) ?  "_generic_next_prime" :
-                           "_generic_prev_prime" );
+    switch (ix) {
+      case 0:  _vcallsub("_generic_next_prime");     break;
+      case 1:  _vcallsub("_generic_prev_prime");     break;
+      default: _vcallsub("PP::nth_prime");           break;
+    }
     return; /* skip implicit PUTBACK */
 
 void
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 9934644..d98036e 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -60,16 +60,9 @@ sub import {
 sub _import_nobigint {
   $_Config{'nobigint'} = 1;
   return unless $_Config{'xs'};
- #undef *prime_count;     *prime_count       = \&_XS_prime_count;
-  undef *nth_prime;       *nth_prime         = \&_XS_nth_prime;
   undef *is_pseudoprime;  *is_pseudoprime    = \&_XS_is_pseudoprime;
   undef *chebyshev_theta; *chebyshev_theta   = \&_XS_chebyshev_theta;
   undef *chebyshev_psi;   *chebyshev_psi     = \&_XS_chebyshev_psi;
-  # These should be fast anyway, but this skips validation.
-  undef *is_prime;        *is_prime          = \&_XS_is_prime;
-  undef *is_prob_prime;   *is_prob_prime     = \&_XS_is_prob_prime;
-  undef *next_prime;      *next_prime        = \&_XS_next_prime;
-  undef *prev_prime;      *prev_prime        = \&_XS_prev_prime;
   1;
 }
 
@@ -113,6 +106,8 @@ BEGIN {
     *euler_phi     = \&Math::Prime::Util::_generic_euler_phi;
     *moebius       = \&Math::Prime::Util::_generic_moebius;
     *mertens       = \&Math::Prime::Util::_generic_mertens;
+    *prime_count   = \&Math::Prime::Util::_generic_prime_count;
+    *nth_prime     = \&Math::Prime::Util::PP::nth_prime;
     *carmichael_lambda = \&Math::Prime::Util::_generic_carmichael_lambda;
     *kronecker     = \&Math::Prime::Util::_generic_kronecker;
     *divisor_sum   = \&Math::Prime::Util::_generic_divisor_sum;
@@ -596,10 +591,10 @@ sub primes {
     # consumes the minimum amount of randomness needed.  But it isn't feasible
     # with large values.  Also note that low must be a prime.
     if ($high <= 262144 && $high <= $_XS_MAXVAL) {
-      my $li     = _XS_prime_count(2, $low);
-      my $irange = _XS_prime_count($low, $high);
+      my $li     = prime_count(2, $low);
+      my $irange = prime_count($low, $high);
       my $rand = $_RANDF->($irange-1);
-      return _XS_nth_prime($li + $rand);
+      return nth_prime($li + $rand);
     }
 
     $low-- if $low == 2;  # Low of 2 becomes 1 for our program.
@@ -801,12 +796,12 @@ sub primes {
     } else {
       my $beg = ($low <= 2)  ?  2  :  next_prime($low-1);
       my $end = ($high < ~0)  ?  prev_prime($high + 1)  :  prev_prime($high);
-      ($istart, $irange) = ( _XS_prime_count(2, $beg), _XS_prime_count($beg, 
$end) );
+      ($istart, $irange) = ( prime_count(2, $beg), prime_count($beg, $end) );
       $_random_cache_small{$low,$high} = [$istart, $irange];
     }
     _set_randf() unless defined $_RANDF;
     my $rand = $_RANDF->($irange-1);
-    return _XS_nth_prime($istart + $rand);
+    return nth_prime($istart + $rand);
   }
 
   sub random_prime {
@@ -1380,7 +1375,7 @@ sub prime_iterator {
   _validate_num($start) || _validate_positive_integer($start);
   my $p = ($start > 0) ? $start-1 : 0;
   if (ref($p) ne 'Math::BigInt' && $p <= $_XS_MAXVAL) {
-    return sub { $p = _XS_next_prime($p); return $p; };
+    return sub { $p = next_prime($p); return $p; };
   } elsif ($_HAVE_GMP) {
     return sub { $p = $p-$p+Math::Prime::Util::GMP::next_prime($p); return 
$p;};
   } else {
@@ -1654,7 +1649,7 @@ sub _generic_kronecker {
   return Math::Prime::Util::PP::kronecker(@_);
 }
 
-sub prime_count {
+sub _generic_prime_count {
   my($low,$high) = @_;
   if (defined $high) {
     _validate_num($low) || _validate_positive_integer($low);
@@ -1665,23 +1660,6 @@ sub prime_count {
   }
   return 0 if $high < 2  ||  $low > $high;
 
-  if ($high <= $_XS_MAXVAL) {
-    if ($high > 4_000_000) {
-      # These estimates need a lot of work.
-      #my $est_segment = 10.0 * 1.5**(log($high / 10**16) / log(10))
-      #                  + (($high-$low)/10**12);
-      #my $est_lehmer = 0.0000000057 * $high**0.72
-      #                 + 0.0000000057 * $low**0.72;
-      #if ($est_lehmer < $est_segment) {
-      if ( ($high / ($high-$low+1)) < 100 ) {
-        my $count;
-        $count  =  _XS_LMO_pi($high);
-        $count -=  _XS_LMO_pi($low-1) if $low > 2;
-        return $count;
-      }
-    }
-    return _XS_prime_count($low,$high);
-  }
   # We can relax these constraints if MPU::GMP gets a fast implementation.
   return Math::Prime::Util::GMP::prime_count($low,$high) if $_HAVE_GMP
                        && defined &Math::Prime::Util::GMP::prime_count
@@ -1691,16 +1669,6 @@ sub prime_count {
   return Math::Prime::Util::PP::prime_count($low,$high);
 }
 
-sub nth_prime {
-  my($n) = @_;
-  _validate_num($n) || _validate_positive_integer($n);
-
-  return _XS_nth_prime($n)
-    if $n <= $_XS_MAXVAL && $n < MPU_MAXPRIMEIDX;
-
-  return Math::Prime::Util::PP::nth_prime($n);
-}
-
 sub _generic_factor {
   my($n) = @_;
   _validate_num($n) || _validate_positive_integer($n);
@@ -1930,8 +1898,7 @@ sub is_provable_prime {
   return 0 if defined $n && $n < 2;
   _validate_num($n) || _validate_positive_integer($n);
 
-  return _XS_is_prime($n)
-    if $n <= $_XS_MAXVAL;
+  return is_prime($n) if $n <= $_XS_MAXVAL;
   return Math::Prime::Util::GMP::is_provable_prime($n)
          if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_provable_prime;
 
@@ -1954,7 +1921,7 @@ sub is_provable_prime_with_cert {
   my $header = "[MPU - Primality Certificate]\nVersion 1.0\n\nProof for:\nN 
$n\n\n";
 
   if ($n <= $_XS_MAXVAL) {
-    my $isp = _XS_is_prime("$n");
+    my $isp = is_prime("$n");
     return ($isp, '') unless $isp == 2;
     return (2, "[MPU - Primality Certificate]\nVersion 1.0\n\nProof for:\nN 
$n\n\nType Small\nN $n\n");
   }
@@ -2038,7 +2005,7 @@ sub prime_count_approx {
   _validate_num($x) || _validate_positive_integer($x);
 
   # With XS using 30k tables, this is super fast.
-  return _XS_prime_count(2,$x) if $x < $_XS_MAXVAL && $x < 3_000_000;
+  return prime_count($x) if $x < $_XS_MAXVAL && $x < 3_000_000;
   # Give an exact answer for what we have in our little table.
   return _tiny_prime_count($x) if $x < $_primes_small[-1];
 
@@ -2089,7 +2056,7 @@ sub prime_count_lower {
   _validate_num($x) || _validate_positive_integer($x);
 
   # With XS using 30k tables, this is super fast.
-  return _XS_prime_count(2,$x) if $x < $_XS_MAXVAL && $x < 3_000_000;
+  return prime_count($x) if $x < $_XS_MAXVAL && $x < 3_000_000;
   # Give an exact answer for what we have in our little table.
   return _tiny_prime_count($x) if $x < $_primes_small[-1];
 
@@ -2139,7 +2106,7 @@ sub prime_count_upper {
   _validate_num($x) || _validate_positive_integer($x);
 
   # With XS using 30k tables, this is super fast.
-  return _XS_prime_count(2,$x) if $x < $_XS_MAXVAL && $x < 3_000_000;
+  return prime_count($x) if $x < $_XS_MAXVAL && $x < 3_000_000;
   # Give an exact answer for what we have in our little table.
   return _tiny_prime_count($x) if $x < $_primes_small[-1];
 
diff --git a/t/13-primecount.t b/t/13-primecount.t
index 0947e2e..8c10cba 100644
--- a/t/13-primecount.t
+++ b/t/13-primecount.t
@@ -163,7 +163,7 @@ SKIP: {
   #is(Math::Prime::Util::_XS_legendre_pi(66123456),3903023,"XS Legendre 
count");
   #is(Math::Prime::Util::_XS_LMOS_pi    (66123456),3903023,"XS LMOS count");
   is(Math::Prime::Util::_XS_LMO_pi     (66123456), 3903023,"XS LMO count");
-  is(Math::Prime::Util::_XS_prime_count(66123456), 3903023,"XS sieve count");
+  is(Math::Prime::Util::_XS_segment_pi (66123456), 3903023,"XS segment count");
 }
 is(Math::Prime::Util::PP::_lehmer_pi   (1456789), 111119, "PP Lehmer count");
 is(Math::Prime::Util::PP::_sieve_prime_count(1456789), 111119, "PP sieve 
count");

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