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