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