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
