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