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