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 b1c0afc7ae2d25105f49e6a4f5a9317aefc60cc3
Author: Dana Jacobsen <d...@acm.org>
Date: Thu Nov 22 18:54:09 2012 -0800
Let AKS in XS work with larger inputs.
---
aks.c | 35 +++++++++++++++--------------------
lib/Math/Prime/Util.pm | 19 ++++++++++---------
2 files changed, 25 insertions(+), 29 deletions(-)
diff --git a/aks.c b/aks.c
index d37b6ac..43a116f 100644
--- a/aks.c
+++ b/aks.c
@@ -21,8 +21,7 @@
#include "sieve.h"
#include "factor.h"
#include "cache.h"
-
-#define addmod(n,a,m) ((((m)-(n)) > (a)) ? ((n)+(a)) : ((n)+(a)-(m)))
+#include "mulmod.h"
static UV log2floor(UV n) {
UV log2n = 0;
@@ -80,7 +79,11 @@ static void poly_mod_mul(UV* px, UV* py, UV* res, UV r, UV
mod)
pyj = py[j];
if (pyj == 0) continue;
rindex = (i+j) < r ? i+j : i+j-r; /* (i+j) % r */
- res[rindex] = (res[rindex] + (pxi*pyj) ) % mod;
+ if (mod < HALF_WORD) {
+ res[rindex] = (res[rindex] + (pxi*pyj) ) % mod;
+ } else {
+ res[rindex] = muladdmod(pxi, pyj, res[rindex], mod);
+ }
}
}
memcpy(px, res, r * sizeof(UV)); /* put result in px */
@@ -91,10 +94,6 @@ static void poly_mod_sqr(UV* px, UV* res, UV r, UV mod)
UV sum, rindex;
UV degree = r-1;
- /* we sum a max of r*mod*mod between modulos */
- if (mod > sqrt(UV_MAX/r))
- return poly_mod_mul(px, px, res, r, mod);
-
memset(res, 0, r * sizeof(UV)); /* zero out sums */
for (d = 0; d <= 2*degree; d++) {
sum = 0;
@@ -112,18 +111,22 @@ static UV* poly_mod_pow(UV* pn, UV power, UV r, UV mod)
{
UV* res;
UV* temp;
+ int use_sqr = (mod > sqrt(UV_MAX/r)) ? 0 : 1;
Newz(0, res, r, UV);
New(0, temp, r, UV);
if ( (res == 0) || (temp == 0) )
- croak("Couldn't allocate space for polynomial of degree %lu\n", r);
+ croak("Couldn't allocate space for polynomial of degree %lu\n", (unsigned
long) r);
res[0] = 1;
while (power) {
if (power & 1) poly_mod_mul(res, pn, temp, r, mod);
power >>= 1;
- if (power) poly_mod_sqr(pn, temp, r, mod);
+ if (power) {
+ if (use_sqr) poly_mod_sqr(pn, temp, r, mod);
+ else poly_mod_mul(pn, pn, temp, r, mod);
+ }
}
Safefree(temp);
return res;
@@ -138,7 +141,7 @@ static int test_anr(UV a, UV n, UV r)
Newz(0, pn, r, UV);
if (pn == 0)
- croak("Couldn't allocate space for polynomial of degree %lu\n", r);
+ croak("Couldn't allocate space for polynomial of degree %lu\n", (unsigned
long) r);
a %= r;
pn[0] = a;
pn[1] = 1;
@@ -160,14 +163,6 @@ int _XS_is_aks_prime(UV n)
double log2n;
int verbose = _XS_get_verbose();
- /* Check for overflow */
-#if BITS_PER_WORD == 32
- if (n >= UVCONST(65535))
-#else
- if (n >= UVCONST(4294967295))
-#endif
- croak("aks(%"UVuf") overflow", n);
-
if (n < 2)
return 0;
if (n == 2)
@@ -180,7 +175,7 @@ int _XS_is_aks_prime(UV n)
log2n = log(n) / log(2); /* C99 has a log2() function */
limit = (UV) floor(log2n * log2n);
- if (verbose) { printf("# aks limit is %lu\n", limit); }
+ if (verbose) { printf("# aks limit is %lu\n", (unsigned long) limit); }
for (r = 2; r < n; r++) {
if ((n % r) == 0)
@@ -198,7 +193,7 @@ int _XS_is_aks_prime(UV n)
rlimit = (UV) floor(sqrt(r-1) * log2n);
- if (verbose) { printf("# aks r = %lu rlimit = %lu\n", r, rlimit); }
+ if (verbose) { printf("# aks r = %lu rlimit = %lu\n", (unsigned long) r,
(unsigned long) rlimit); }
for (a = 1; a <= rlimit; a++) {
if (! test_anr(a, n, r) )
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 7e570a9..a6d1d36 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -82,11 +82,13 @@ BEGIN {
*pminus1_factor = \&Math::Prime::Util::PP::pminus1_factor;
};
- # See if they have the GMP module
$_Config{'gmp'} = 0;
- $_Config{'gmp'} = 1 if eval { require Math::Prime::Util::GMP;
- Math::Prime::Util::GMP->import();
- 1; };
+ # See if they have the GMP module and haven't requested it not to be used.
+ if (!defined $ENV{MPU_NO_GMP} || $ENV{MPU_NO_GMP} != 1) {
+ $_Config{'gmp'} = 1 if eval { require Math::Prime::Util::GMP;
+ Math::Prime::Util::GMP->import();
+ 1; };
+ }
}
END {
_prime_memfreeall;
@@ -819,7 +821,7 @@ sub _omega {
sub is_prime {
my($n) = @_;
- return 0 if $n <= 0;
+ return 0 if defined $n && $n < 2;
_validate_positive_integer($n);
return _XS_is_prime($n) if $n <= $_XS_MAXVAL;
@@ -829,11 +831,10 @@ sub is_prime {
sub is_aks_prime {
my($n) = @_;
- return 0 if $n <= 0;
+ return 0 if defined $n && $n < 2;
_validate_positive_integer($n);
- my $max_xs = ($_Config{'maxparam'} > 4294967295) ? 4294967294 : 65534;
- return _XS_is_aks_prime($n) if $n <= $_XS_MAXVAL && $n <= $max_xs;
+ return _XS_is_aks_prime($n) if $n <= $_XS_MAXVAL;
return Math::Prime::Util::GMP::is_aks_prime($n) if $_HAVE_GMP
&& defined &Math::Prime::Util::GMP::is_aks_prime;
return Math::Prime::Util::PP::is_aks_prime($n);
@@ -904,7 +905,7 @@ sub prime_count {
sub _prime_count_lehmer {
my($n) = @_;
- return 0 if $n <= 0;
+ return 0 if defined $n && $n < 2;
_validate_positive_integer($n);
return _XS_lehmer_pi($n) if $n <= $_XS_MAXVAL;
--
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
