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 99042b204d0875e3fd1bfea9e49f5f95772b3ee5
Author: Dana Jacobsen <d...@acm.org>
Date: Fri Sep 27 17:51:03 2013 -0700
Make factor consistent in scalar context
---
Changes | 5 +++++
TODO | 7 +++++++
XS.xs | 10 +++++++---
factor.c | 2 +-
lib/Math/Prime/Util.pm | 10 +++++++++-
lib/Math/Prime/Util/PP.pm | 11 +++++++----
t/50-factoring.t | 12 +++++++++++-
7 files changed, 47 insertions(+), 10 deletions(-)
diff --git a/Changes b/Changes
index 2eaea16..7e34d7a 100644
--- a/Changes
+++ b/Changes
@@ -49,6 +49,11 @@ Revision history for Perl module Math::Prime::Util
- Speedup for Perl (no GMP) primality and random nbit primes.
+ - factor() can be called in scalar context to give the number of
+ prime factors. The XS function was ignoring the context, and now
+ is more consistent. It also slightly speeds up looking at the
+ number of factors, e.g. Omega(x) A001222.
+
0.31 2013-08-07
- Change proof certificate documentation to reflect the new text format.
diff --git a/TODO b/TODO
index 3ca6697..4dd824b 100644
--- a/TODO
+++ b/TODO
@@ -46,3 +46,10 @@
(1) optional second argument. Easily handled, and not hard to do in
generic sub call.
(2) generic sub returns an array. This is the sticking point.
+
+- Factoring in PP code is really wasteful -- we're calling _isprime7 before
+ we've done enough trial division, and later we're calling it on known
+ composites. Note how the XS code splits the factor code into the public
+ API (small factors, isprime, then call main code) and main code (just the
+ algorithm). The PP code isn't doing that, which means we're doing lots of
+ extra primality checks, which aren't cheap in PP.
diff --git a/XS.xs b/XS.xs
index b6cd063..401af40 100644
--- a/XS.xs
+++ b/XS.xs
@@ -402,9 +402,13 @@ _XS_factor(IN UV n)
int i, nfactors;
PPCODE:
nfactors = factor(n, factors);
- EXTEND(SP, nfactors);
- for (i = 0; i < nfactors; i++) {
- PUSHs(sv_2mortal(newSVuv( factors[i] )));
+ if (GIMME_V == G_SCALAR) {
+ PUSHs(sv_2mortal(newSVuv(nfactors)));
+ } else if (GIMME_V == G_ARRAY) {
+ EXTEND(SP, nfactors);
+ for (i = 0; i < nfactors; i++) {
+ PUSHs(sv_2mortal(newSVuv( factors[i] )));
+ }
}
void
diff --git a/factor.c b/factor.c
index 82d09c7..ab1c77d 100644
--- a/factor.c
+++ b/factor.c
@@ -161,7 +161,7 @@ int trial_factor(UV n, UV *factors, UV maxtrial)
if (maxtrial == 0) maxtrial = UV_MAX;
/* Cover the cases 0/1/2/3 now */
- if ( (n < 4) || (maxtrial < 4) ) {
+ if (n < 4 || maxtrial < 2) {
factors[0] = n;
return 1;
}
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 0c5cd10..49e7008 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -3090,6 +3090,10 @@ Returning composite for all non-2 even input makes the
function match most
other implementations including L<Math::Primality>'s C<is_strong_pseudoprime>
function.
+=head2 miller_rabin
+
+An alias for C<is_strong_pseudoprime>. This name is deprecated.
+
=head2 is_lucas_pseudoprime
Takes a positive number as input, and returns 1 if the input is a standard
@@ -4018,6 +4022,10 @@ guarantees multiplying the factors together will always
result in the
input value, though those are the only cases where the returned factors
are not prime.
+In scalar context, returns the number of prime factors with multiplicity
+(L<OEIS A001222|http://oeis.org/A001222>). This is the expected result,
+as if we put the result into an array and then took the scalar result.
+
The current algorithm for non-bigints is a sequence of small trial division,
a few rounds of Pollard's Rho, SQUFOF, Pollard's p-1, Hart's OLF, a long
run of Pollard's Rho, and finally trial division if anything survives. This
@@ -4353,7 +4361,7 @@ Project Euler, problem 187, stupid brute force solution,
~4 minutes:
use Math::Prime::Util qw/factor -nobigint/;
my $nsemis = 0;
- do { my @f = factor($_); $nsemis++ if scalar @f == 2; }
+ do { $nsemis++ if scalar factor($_) == 2; }
for 1 .. int(10**8)-1;
say $nsemis;
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index aaa130a..31f835c 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -1398,10 +1398,12 @@ sub trial_factor {
_validate_positive_integer($n);
$maxlim = $n unless defined $maxlim && _validate_positive_integer($maxlim);
- # Don't use _basic factor here -- they want a trial forced.
- #my @factors = _basic_factor($n);
- return ($n) if $n < 4;
+ # Don't use _basic_factor here -- they want a trial forced.
my @factors;
+ if ($n < 4) {
+ @factors = ($n);
+ return @factors;
+ }
while ( !($n % 2) ) { push @factors, 2; $n = int($n / 2); }
while ( !($n % 3) ) { push @factors, 3; $n = int($n / 3); }
while ( !($n % 5) ) { push @factors, 5; $n = int($n / 5); }
@@ -1499,7 +1501,8 @@ sub factor {
}
push @factors, $n if $n != 1;
}
- sort {$a<=>$b} @factors;
+ @factors = sort {$a<=>$b} @factors;
+ return @factors;
}
sub _found_factor {
diff --git a/t/50-factoring.t b/t/50-factoring.t
index 8365d7a..042975b 100644
--- a/t/50-factoring.t
+++ b/t/50-factoring.t
@@ -74,7 +74,7 @@ my %all_factors = (
0 => [],
);
-plan tests => (2 * scalar @testn) + scalar(keys %all_factors) + 10*9 + 1;
+plan tests => (2 * scalar @testn) + scalar(keys %all_factors) + 10*9 + 8 + 1;
foreach my $n (@testn) {
my @f = factor($n);
@@ -126,3 +126,13 @@ sub extra_factor_test {
is_deeply( [ sort {$a<=>$b} $fsub->(403) ], [13, 31], "$fname(403)" );
is_deeply( [ sort {$a<=>$b} $fsub->(549900) ], [2,2,3,3,5,5,13,47],
"$fname(549900)" );
}
+
+# Factor in scalar context
+is( scalar factor(0), 1, "scalar factor(0) should be 1" );
+is( scalar factor(1), 1, "scalar factor(1) should be 1" );
+is( scalar factor(3), 1, "scalar factor(3) should be 1" );
+is( scalar factor(4), 2, "scalar factor(4) should be 2" );
+is( scalar factor(5), 1, "scalar factor(5) should be 1" );
+is( scalar factor(6), 2, "scalar factor(6) should be 2" );
+is( scalar factor(30107), 4, "scalar factor(30107) should be 4" );
+is( scalar factor(174636000), 15, "scalar factor(174636000) should be 15" );
--
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
