This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.32 in repository libmath-prime-util-perl.
commit fa31f4e79278281cde725e9e7ed86b8d65fae589 Author: Dana Jacobsen <d...@acm.org> Date: Fri Oct 11 19:23:46 2013 -0700 Tiny PP factor speedup --- README | 2 +- lib/Math/Prime/Util/PP.pm | 33 +++++++++++++++++++-------------- 2 files changed, 20 insertions(+), 15 deletions(-) diff --git a/README b/README index e230a11..1754866 100644 --- a/README +++ b/README @@ -18,7 +18,7 @@ Current measurements show it is faster than: Crypt::Primes For non-bignums, it is typically faster than Math::Pari (and doesn't require Pari to be installed). With Math::Prime::Util::GMP installed -it is usually faster than Math::Pari for bigints; +it is usually faster than Math::Pari for bigints. SYNOPSIS diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index b339999..7bad4f1 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -664,17 +664,21 @@ sub _mulmod { my($a, $b, $m) = @_; return (($a * $b) % $m) if ($a|$b) < $_half_word; my $r = 0; - while ($b > 0) { - if ($b & 1) { - if ($r == 0) { - $r = $a; - } else { - $r = $m - $r; - $r = ($a >= $r) ? $a - $r : $m - $r + $a; - } + $a %= $m if $a >= $m; + $b %= $m if $b >= $m; + ($a,$b) = ($b,$a) if $a < $b; + if ($m <= (~0 >> 1)) { + while ($b > 0) { + if ($b & 1) { $r += $a; $r -= $m if $r >= $m; } + $b >>= 1; + if ($b) { $a += $a; $a -= $m if $a >= $m; } + } + } else { + while ($b > 0) { + if ($b & 1) { $r = $m-$r; $r = ($a >= $r) ? $a-$r : $m-$r+$a; } + $b >>= 1; + if ($b) { $a = ($a > ($m - $a)) ? ($a - $m) + $a : $a + $a; } } - $a = ($a > ($m - $a)) ? ($a - $m) + $a : $a + $a; - $b >>= 1; } $r; } @@ -1458,10 +1462,11 @@ sub factor { return trial_factor($n) if $n < 1_000_000; - my @factors = _basic_factor($n); - return @factors if $n < 4; - - # Use 'n = int($n/7)' instead of 'n/=7' to not "upgrade" n to a Math::BigFloat. + my @factors; + # Use 'n=int($n/7)' instead of 'n/=7' to not "upgrade" n to a Math::BigFloat. + while (($n % 2) == 0) { push @factors, 2; $n = int($n / 2); } + while (($n % 3) == 0) { push @factors, 3; $n = int($n / 3); } + while (($n % 5) == 0) { push @factors, 5; $n = int($n / 5); } while (($n % 7) == 0) { push @factors, 7; $n = int($n / 7); } while (($n % 11) == 0) { push @factors, 11; $n = int($n / 11); } while (($n % 13) == 0) { push @factors, 13; $n = int($n / 13); } -- 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