This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.40
in repository libmath-prime-util-perl.
commit dd6d9998dfbdcca4a63cd21b0056db3ace41445c
Author: Dana Jacobsen <d...@acm.org>
Date: Wed Mar 5 13:47:02 2014 -0800
Speedup exp_mangoldt for large numbers -- primality + power detection
instead of factoring
---
lib/Math/Prime/Util/PP.pm | 10 +++++++---
t/22-aks-prime.t | 8 +++-----
2 files changed, 10 insertions(+), 8 deletions(-)
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index f03a0c0..9855eac 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -752,10 +752,14 @@ sub exp_mangoldt {
return 1 if defined $n && $n <= 1; # n <= 1
return 2 if ($n & ($n-1)) == 0; # n power of 2
return 1 unless $n & 1; # even n can't be p^m
+ return $n if Math::Prime::Util::is_prob_prime($n); # prime n returns n
- my @pe = Math::Prime::Util::factor_exp($n);
- return 1 if scalar @pe > 1;
- return $pe[0]->[0];
+ my $k = Math::Prime::Util::is_power($n);
+ if ($k >= 2) {
+ my $root = Math::BigInt->new("$n")->broot($k);
+ return $root if Math::Prime::Util::is_prob_prime($root);
+ }
+ 1;
}
sub carmichael_lambda {
diff --git a/t/22-aks-prime.t b/t/22-aks-prime.t
index 7418599..8aa19bd 100644
--- a/t/22-aks-prime.t
+++ b/t/22-aks-prime.t
@@ -25,11 +25,9 @@ ok(!is_aks_prime(-2), '-2 is not prime');
# Simple number (cought by sqrt test)
is( is_aks_prime(877), 1, "is_aks_prime(877) is true" );
-# Perhaps let them know this is probably not a hung test?
-# This runs in milliseconds on an i3930K, but 1.5 minutes on an UltraSPARC.
-# These are the smallest numbers that actually run the code, so I don't know
-# how to make them run any faster. On the 32-bit UltraSPARC, it's the mulmod
-# that is painfully slow.
+# This test can take a very long time if mulmods are very slow (e.g. on
+# UltraSPARC). With the B+V improvements this should be fast enough for
+# the little example that we are ok.
#diag "Unfortunately these tests are very slow.";
--
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
