This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.14 in repository libmath-prime-util-perl.
commit 3e5a8b2eda5466f1126a7039b06ae11947daae1d Author: Dana Jacobsen <d...@acm.org> Date: Wed Nov 28 22:28:21 2012 -0800 Tweak MR test, add environment variables to disable XS and GMP --- Changes | 3 +++ TODO | 7 +++++-- factor.c | 25 ++++++++++++------------- lib/Math/Prime/Util.pm | 6 ++++-- 4 files changed, 24 insertions(+), 17 deletions(-) diff --git a/Changes b/Changes index 72b964e..86c6544 100644 --- a/Changes +++ b/Changes @@ -16,6 +16,9 @@ Revision history for Perl extension Math::Prime::Util. jordan_totient generalization of Euler Totient divisor_sum run coderef for every divisor + - Allow environment variables MPU_NO_XS and MPU_NO_GMP to turn off XS and + GMP support respectively if they are defined and equal to 1. + 0.13 19 November 2012 - Fix an issue with prime count, and make prime count available as a diff --git a/TODO b/TODO index e317e7f..daade6c 100644 --- a/TODO +++ b/TODO @@ -29,8 +29,6 @@ - Make proper pminus1 in PP code, like factor.c. -- Add Lehmer in PP (I have a version, just needs some polishing). - - For bignums, RiemannZeta and RiemmannR are slow and give questionable precision. We should be able to do better. One problem is the accuracy bug in Math::BigFloat. Perhaps check for Math::MPFR installed and use it? @@ -47,3 +45,8 @@ is_provable_prime RiemannZeta RiemannR + +- Add Lehmer in PP (I have a version, just needs some polishing). This is a + high priority, as the test suite now assumes prime_count is fast for large + inputs. + diff --git a/factor.c b/factor.c index deedbae..a032cbe 100644 --- a/factor.c +++ b/factor.c @@ -142,9 +142,9 @@ static int is_perfect_square(UV n, UV* sqrtn) */ int _XS_miller_rabin(UV n, const UV *bases, int nbases) { - int b; - int s = 0; + UV const nm1 = n-1; UV d = n-1; + int b, r, s = 0; MPUassert(n > 3, "MR called with n <= 3"); @@ -153,15 +153,18 @@ int _XS_miller_rabin(UV n, const UV *bases, int nbases) d >>= 1; } for (b = 0; b < nbases; b++) { - int r; - UV a = bases[b]; - UV x; + UV x, a = bases[b]; if (a < 2) croak("Base %"UVuf" is invalid", a); #if 0 if (a > (n-2)) croak("Base %"UVuf" is invalid for input %"UVuf, a, n); +#else + if (a >= n) + a %= n; + if ( (a <= 1) || (a == nm1) ) + continue; #endif /* n is a strong pseudoprime to this base if either @@ -170,19 +173,15 @@ int _XS_miller_rabin(UV n, const UV *bases, int nbases) */ x = powmod(a, d, n); - if ( (x == 1) || (x == (n-1)) ) continue; + if ( (x == 1) || (x == nm1) ) continue; /* cover r = 1 to s-1, r=0 was just done */ for (r = 1; r < s; r++) { x = sqrmod(x, n); - if (x == 1) { - return 0; - } else if (x == (n-1)) { - a = 0; - break; - } + if ( x == nm1 ) break; + if ( x == 1 ) return 0; } - if (a != 0) + if (r >= s) return 0; } return 1; diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index e40c547..0df6425 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -59,6 +59,7 @@ BEGIN { require Math::Prime::Util::PP; Math::Prime::Util::PP->import(); eval { + return 0 if defined $ENV{MPU_NO_XS} && $ENV{MPU_NO_XS} == 1; require XSLoader; XSLoader::load(__PACKAGE__, $Math::Prime::Util::VERSION); prime_precalc(0); @@ -276,8 +277,9 @@ sub primes { } elsif (($high <= (65536*30)) || ($high <= _get_prime_cache_size())) { $method = 'Sieve'; - # More memory than we should reasonably use for base sieve? - } elsif ($high > (32*1024*1024*30)) { + # At some point the segmented sieve is faster than the base sieve, not + # to mention using much less memory. + } elsif ($high > (1024*1024*30)) { $method = 'Segment'; # The segment sieve doesn't itself use a segmented sieve for the base, # so it will slow down for very large endpoints (larger than 10^16). -- 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