This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.10
in repository libmath-prime-util-perl.
commit cc7c8a4be3dc0ce5a7f2066c3c43f1f2524ae261
Author: Dana Jacobsen <d...@acm.org>
Date: Thu Jun 28 17:22:36 2012 -0600
Speed up random_ndigit_prime a little for 9+ digits
---
TODO | 2 --
lib/Math/Prime/Util.pm | 21 ++++++++++++++++-----
2 files changed, 16 insertions(+), 7 deletions(-)
diff --git a/TODO b/TODO
index da5c284..a879bfd 100644
--- a/TODO
+++ b/TODO
@@ -20,8 +20,6 @@
- Faster SQUFOF
-- speed up random_prime for large numbers
-
- better prime count upper/lower bounds
- Move .c / .h files into separate directory.
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index a6038d7..0d1ff4f 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -171,7 +171,6 @@ sub random_prime {
$low = 2 if $low < 2;
# Make sure we have a valid range.
- # TODO: this is is killing performance with large numbers
$low = next_prime($low - 1);
$high = ($high < ~0) ? prev_prime($high + 1) : prev_prime($high);
return $low if ($low == $high) && is_prime($low);
@@ -181,6 +180,10 @@ sub random_prime {
my $range = $high - $low + 1;
my $prime;
+ # If $low is large (e.g. >10 digits) and $range is small (say ~10k), it
+ # would be fastest to call primes in the range and randomly pick one. I'm
+ # not implementing it now because it seems like a rare case.
+
# Note: I was using rand($range), but Math::Random::MT ignores the argument
# instead of following its documentation.
my $irandf = (defined &::rand) ? sub { return int(::rand()*shift); }
@@ -207,15 +210,23 @@ sub random_prime {
}
+# Calculate next_prime and prev_prime once.
+# This helps performance with 9+ digits.
+my @_random_ndigit_ranges;
+
sub random_ndigit_prime {
my $digits = shift;
if ((!defined $digits) || ($digits > $_maxdigits) || ($digits < 1)) {
croak "Digits must be between 1 and $_maxdigits";
}
- my $low = ($digits == 1) ? 0 : int(10 ** ($digits-1));
- my $max = int(10 ** $digits);
- $max = ~0 if $max > ~0;
- return random_prime($low, $max);
+ if (!defined $_random_ndigit_ranges[$digits]) {
+ my $low = ($digits == 1) ? 0 : int(10 ** ($digits-1));
+ my $high = int(10 ** $digits);
+ $high = ~0 if $high > ~0;
+ $_random_ndigit_ranges[$digits] = [next_prime($low), prev_prime($high)];
+ }
+ my ($low, $high) = @{$_random_ndigit_ranges[$digits]};
+ return random_prime($low, $high);
}
# Perhaps a random_nbit_prime ? Definition?
--
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
