This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.37 in repository libmath-prime-util-perl.
commit 14e86ff4d2dec82b228e2284dc536f33a5940abd Author: Dana Jacobsen <d...@acm.org> Date: Fri Jan 17 18:24:18 2014 -0800 Simplify primes() --- Changes | 7 +++++ TODO | 3 --- lib/Math/Prime/Util.pm | 69 ++++++++++++++++------------------------------- lib/Math/Prime/Util/PP.pm | 19 ++++++------- t/11-primes.t | 43 ++++++++++++++++++----------- xt/primes-edgecases.pl | 34 +++++++++++------------ 6 files changed, 80 insertions(+), 95 deletions(-) diff --git a/Changes b/Changes index 2c9ade8..f8f8deb 100644 --- a/Changes +++ b/Changes @@ -1,5 +1,12 @@ Revision history for Perl module Math::Prime::Util +0.37 2014-02 + + [FUNCTIONALITY AND PERFORMANCE] + + - Simplified primes(). No longer takes an optional hashref as first arg, + which was awkward and never documented. + 0.36 2014-01-13 [API Changes] diff --git a/TODO b/TODO index 1bd642b..1881492 100644 --- a/TODO +++ b/TODO @@ -29,9 +29,6 @@ - Big features: - QS factoring -- segment sieve should itself use a segment for its primes. - Today we'd need sqrt(2^64) max = 140MB. Segmenting would yield under 1MB. - - Figure out a way to make the internal FOR_EACH_PRIME macros use a segmented sieve. diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 0b2321a..53ef540 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -276,14 +276,14 @@ sub _tiny_prime_count { ############################################################################# sub primes { - my $optref = (ref $_[0] eq 'HASH') ? shift : {}; - croak "no parameters to primes" unless scalar @_ > 0; - croak "too many parameters to primes" unless scalar @_ <= 2; - my $low = (@_ == 2) ? shift : 2; - my $high = shift; - - _validate_num($low) || _validate_positive_integer($low); - _validate_num($high) || _validate_positive_integer($high); + my($low,$high) = @_; + if (scalar @_ > 1) { + _validate_num($low) || _validate_positive_integer($low); + _validate_num($high) || _validate_positive_integer($high); + } else { + ($low,$high) = (2, $low); + _validate_num($high) || _validate_positive_integer($high); + } my $sref = []; return $sref if ($low > $high) || ($high < 2); @@ -302,54 +302,31 @@ sub primes { return Math::Prime::Util::PP::primes($low,$high); } - my $method = $optref->{'method'}; - $method = 'Dynamic' unless defined $method; + # Decide the method to use. We have four to choose from: + # 1. Trial No memory, no overhead, but more time per prime. + # 2. Sieve Monolithic cached sieve. + # 3. Erat Monolithic uncached sieve. + # 4. Segment Segment sieve. Never a bad decision. - if ($method =~ /^(Dyn\w*|Default|Generate)$/i) { - # Dynamic -- we should try to do something smart. + if (($low+1) >= $high || # Tiny range, or + $high > 10**14 && ($high-$low) < 50000) { # Small relative range - # Tiny range? - if (($low+1) >= $high) { - $method = 'Trial'; + $sref = trial_primes($low, $high); - # Fast for cached sieve? - } elsif (($high <= (65536*30)) || ($high <= _get_prime_cache_size())) { - $method = 'Sieve'; + } elsif ($high <= (65536*30) || # Very small, or + $high <= _get_prime_cache_size()) { # already in the main cache. - # At some point the segmented sieve is faster than the base sieve, not - # to mention using much less memory. - } elsif ($high > (1024*1024*30)) { - $method = 'Segment'; - # Our segment sieve is pretty good about not using too many resources, - # but with a very small range, it's better to just do trial. - $method = 'Trial' if $high > 10**14 && ($high-$low) < 50000; + $sref = sieve_primes($low, $high); - # Only want half or less of the range low-high ? - } elsif ( int($high / ($high-$low)) >= 2 ) { - $method = 'Segment'; + } else { - } else { - $method = 'Sieve'; - } - } + $sref = segment_primes($low, $high); - if ($method =~ /^Simple\w*$/i) { - carp "Method 'Simple' is deprecated."; - $method = 'Erat'; } - if ($method =~ /^Trial$/i) { $sref = trial_primes($low, $high); } - elsif ($method =~ /^Erat\w*$/i) { $sref = erat_primes($low, $high); } - elsif ($method =~ /^Seg\w*$/i) { $sref = segment_primes($low, $high); } - elsif ($method =~ /^Sieve$/i) { $sref = sieve_primes($low, $high); } - else { croak "Unknown prime method: $method"; } - - # Using this line: + # We could return an array ref in scalar context, array in list context with: # return (wantarray) ? @{$sref} : $sref; - # would allow us to return an array ref in scalar context, and an array - # in array context. Handy for people who might write: - # @primes = primes(100); - # but I think the dual interface could bite us later. + # but I think the dual interface could be confusing, albeit often handy. return $sref; } diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index ad8db7d..db699cc 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -371,20 +371,17 @@ sub trial_primes { } sub primes { - my $optref = (ref $_[0] eq 'HASH') ? shift : {}; - croak "no parameters to primes" unless scalar @_ > 0; - croak "too many parameters to primes" unless scalar @_ <= 2; - my $low = (@_ == 2) ? shift : 2; - my $high = shift; + my($low,$high) = @_; + if (scalar @_ > 1) { + _validate_positive_integer($low); + _validate_positive_integer($high); + } else { + ($low,$high) = (2, $low); + _validate_positive_integer($high); + } my $sref = []; - - _validate_positive_integer($low); - _validate_positive_integer($high); - return $sref if ($low > $high) || ($high < 2); - # Ignore method options in this code - # At some point even the pretty-fast pure perl sieve is going to be a # dog, and we should move to trials. This is typical with a small range # on a large base. More thought on the switchover should be done. diff --git a/t/11-primes.t b/t/11-primes.t index 6a532c2..d419e20 100644 --- a/t/11-primes.t +++ b/t/11-primes.t @@ -7,8 +7,19 @@ use Math::Prime::Util qw/primes prime_count/; my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32; $use64 = 0 if 18446744073709550592 == ~0; +my $usexs = Math::Prime::Util::prime_get_config->{'xs'}; -plan tests => 12+3 + 12 + 1 + 19 + ($use64 ? 1 : 0) + 1 + 13*5; +my %primesubs = ( + trial => \&Math::Prime::Util::trial_primes, + erat => \&Math::Prime::Util::erat_primes, + segment => \&Math::Prime::Util::segment_primes, + sieve => \&Math::Prime::Util::sieve_primes, + primes => \&Math::Prime::Util::primes, +); +# Don't test the private XS methods if we're not using XS. +delete @primesubs{qw/trial erat segment sieve/} unless $usexs; + +plan tests => 12+3 + 12 + 1 + 19 + ($use64 ? 1 : 0) + 1 + 13*scalar(keys(%primesubs)); ok(!eval { primes(undef); }, "primes(undef)"); ok(!eval { primes("a"); }, "primes(a)"); @@ -112,19 +123,19 @@ if ($use64) { is( scalar @{primes(474973,838390)}, prime_count(838390) - prime_count(474973), "count primes within a range" ); - -foreach my $method (qw/trial erat segment sieve dynamic/) { - is_deeply( primes({method=>$method}, 0, 3572), \@small_primes, "Primes between 0 and 3572" ); - is_deeply( primes({method=>$method}, 2, 20), [2,3,5,7,11,13,17,19], "Primes between 2 and 20" ); - is_deeply( primes({method=>$method}, 30, 70), [31,37,41,43,47,53,59,61,67], "Primes between 30 and 70" ); - is_deeply( primes({method=>$method}, 30, 70), [31,37,41,43,47,53,59,61,67], "Primes between 30 and 70" ); - is_deeply( primes({method=>$method}, 20, 2), [], "Primes between 20 and 2" ); - is_deeply( primes({method=>$method}, 1, 1), [], "Primes ($method) between 1 and 1" ); - is_deeply( primes({method=>$method}, 2, 2), [2], "Primes ($method) between 2 and 2" ); - is_deeply( primes({method=>$method}, 3, 3), [3], "Primes ($method) between 3 and 3" ); - is_deeply( primes({method=>$method}, 2010733, 2010733+148), [2010733,2010733+148], "Primegap 21 inclusive" ); - is_deeply( primes({method=>$method}, 2010733+1, 2010733+148-2), [], "Primegap 21 exclusive" ); - is_deeply( primes({method=>$method}, 3088, 3164), [3089,3109,3119,3121,3137,3163], "Primes between 3088 and 3164" ); - is_deeply( primes({method=>$method}, 3089, 3163), [3089,3109,3119,3121,3137,3163], "Primes between 3089 and 3163" ); - is_deeply( primes({method=>$method}, 3090, 3162), [3109,3119,3121,3137], "Primes between 3090 and 3162" ); +# Test individual methods +while (my($method, $sub) = each (%primesubs)) { + is_deeply( $sub->(0, 3572), \@small_primes, "$method(0, 3572)" ); + is_deeply( $sub->(2, 20), [2,3,5,7,11,13,17,19], "$method(2, 20)" ); + is_deeply( $sub->(30, 70), [31,37,41,43,47,53,59,61,67], "$method(30, 70)" ); + is_deeply( $sub->(30, 70), [31,37,41,43,47,53,59,61,67], "$method(30, 70)" ); + is_deeply( $sub->(20, 2), [], "$method(20, 2)" ); + is_deeply( $sub->(1, 1), [], "$method(1, 1)" ); + is_deeply( $sub->(2, 2), [2], "$method(2, 2)" ); + is_deeply( $sub->(3, 3), [3], "$method(3, 3)" ); + is_deeply( $sub->(2010733, 2010733+148), [2010733,2010733+148], "$method Primegap 21 inclusive" ); + is_deeply( $sub->(2010733+1, 2010733+148-2), [], "$method Primegap 21 exclusive" ); + is_deeply( $sub->(3088, 3164), [3089,3109,3119,3121,3137,3163], "$method(3088, 3164)" ); + is_deeply( $sub->(3089, 3163), [3089,3109,3119,3121,3137,3163], "$method(3089, 3163)" ); + is_deeply( $sub->(3090, 3162), [3109,3119,3121,3137], "$method(3090, 3162)" ); } diff --git a/xt/primes-edgecases.pl b/xt/primes-edgecases.pl index 36915f8..1fa4bab 100755 --- a/xt/primes-edgecases.pl +++ b/xt/primes-edgecases.pl @@ -72,37 +72,33 @@ foreach my $bdelta (reverse 0 .. 100) { is_deeply( gen_forprimes($b,$e), \@p, "forprimes {} $b,$e"); } } -diag "\nChecking numbers near end with segment primes(). Very slow.\n"; +diag "\nChecking numbers near end with segment primes().\n"; { my $b = $lprimes[-1] - 1; my $e = ~0; my @p = ($lprimes[-1]); diag "\n Window around $lprimes[-1]\n"; - is_deeply( gen_primes({method => 'Segment'}, $b, $b), [], "primes($b,$b)"); - is_deeply( gen_primes({method => 'Segment'}, $b, $b+1), \@p, "primes($b,$b+1)"); - is_deeply( gen_primes({method => 'Segment'}, $b, $b+2), \@p, "primes($b,$b+2)"); - is_deeply( gen_primes({method => 'Segment'}, $b+1, $b+1), \@p, "primes($b+1,$b+1)"); - is_deeply( gen_primes({method => 'Segment'}, $b+1, $b+2), \@p, "primes($b+1,$b+2)"); - is_deeply( gen_primes({method => 'Segment'}, $b+2, $b+2), [], "primes($b+2,$b+2)"); + is_deeply( gen_segment_primes($b, $b), [], "primes($b,$b)"); + is_deeply( gen_segment_primes($b, $b+1), \@p, "primes($b,$b+1)"); + is_deeply( gen_segment_primes($b, $b+2), \@p, "primes($b,$b+2)"); + is_deeply( gen_segment_primes($b+1, $b+1), \@p, "primes($b+1,$b+1)"); + is_deeply( gen_segment_primes($b+1, $b+2), \@p, "primes($b+1,$b+2)"); + is_deeply( gen_segment_primes($b+2, $b+2), [], "primes($b+2,$b+2)"); diag "\n Window around $e\n"; - is_deeply( gen_primes({method => 'Segment'}, $e-2, $e-2), [], "primes($e-2,$e-2)"); - is_deeply( gen_primes({method => 'Segment'}, $e-2, $e), [], "primes($e-2,$e)"); - is_deeply( gen_primes({method => 'Segment'}, $e-1, $e), [], "primes($e-1,$e)"); - is_deeply( gen_primes({method => 'Segment'}, $e, $e), [], "primes($e,$e)"); + is_deeply( gen_segment_primes($e-2, $e-2), [], "primes($e-2,$e-2)"); + is_deeply( gen_segment_primes($e-2, $e), [], "primes($e-2,$e)"); + is_deeply( gen_segment_primes($e-1, $e), [], "primes($e-1,$e)"); + is_deeply( gen_segment_primes($e, $e), [], "primes($e,$e)"); } -#diag "\nChecking numbers near end with forprimes. This will take a *very* long time.\n"; -#foreach my $bdelta (reverse 0 .. 9) { -# foreach my $edelta (reverse 0 .. $bdelta) { -# my ($b, $e) = (~0 - $bdelta, ~0 - $edelta); -# my @p = grep { $_ >= $b && $_ <= $e } @lprimes; -# is_deeply( gen_forprimes($b,$e), \@p, "forprimes {} $b,$e"); -# } -#} sub gen_primes { return primes(@_); } +sub gen_segment_primes { + my($low, $high) = @_; + return Math::Prime::Util::segment_primes($low,$high); # Private function +} sub gen_forprimes { my($b, $e) = @_; my @p; -- 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