This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.35
in repository libmath-prime-util-perl.
commit 1cd370bff3bdfc3013402b62010f9e03491c0f8f
Author: Dana Jacobsen <d...@acm.org>
Date: Fri Nov 22 18:06:00 2013 -0800
Use XS prime count for small approx/lower/upper
---
lib/Math/Prime/Util.pm | 44 +++++++++++++++++++++++++++++---------------
1 file changed, 29 insertions(+), 15 deletions(-)
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 63ac022..faf70fd 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -240,15 +240,19 @@ my @_primes_small = (
101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,
193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,
293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,
- 409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499);
-my @_prime_count_small = (
- 0,0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8,8,8,9,9,9,9,9,9,10,10,
- 11,11,11,11,11,11,12,12,12,12,13,13,14,14,14,14,15,15,15,15,15,15,
- 16,16,16,16,16,16,17,17,18,18,18,18,18,18,19);
-#my @_prime_next_small = (
-# 2,2,3,5,5,7,7,11,11,11,11,13,13,17,17,17,17,19,19,23,23,23,23,
-# 29,29,29,29,29,29,31,31,37,37,37,37,37,37,41,41,41,41,43,43,47,
-# 47,47,47,53,53,53,53,53,53,59,59,59,59,59,59,61,61,67,67,67,67,67,67,71);
+ 409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509);
+sub _tiny_prime_count {
+ my($n) = @_;
+ return if $n >= $_primes_small[-1];
+ my $j = $#_primes_small;
+ my $i = 1 + ($n >> 4);
+ while ($i < $j) {
+ my $mid = ($i+$j)>>1;
+ if ($_primes_small[$mid] <= $n) { $i = $mid+1; }
+ else { $j = $mid; }
+ }
+ return $i-1;
+}
@@ -2162,7 +2166,10 @@ sub prime_count_approx {
my($x) = @_;
_validate_num($x) || _validate_positive_integer($x);
- return $_prime_count_small[$x] if $x <= $#_prime_count_small;
+ # With XS using 30k tables, this is super fast.
+ return _XS_prime_count(2,$x) if $x < $_XS_MAXVAL && $x < 3_000_000;
+ # Give an exact answer for what we have in our little table.
+ return _tiny_prime_count($x) if $x < $_primes_small[-1];
# Below 2^58th or so, all differences between the high precision and C double
# precision result are less than 0.5.
@@ -2209,9 +2216,13 @@ sub prime_count_lower {
my($x) = @_;
_validate_num($x) || _validate_positive_integer($x);
- return $_prime_count_small[$x] if $x <= $#_prime_count_small;
+ # With XS using 30k tables, this is super fast.
+ return _XS_prime_count(2,$x) if $x < $_XS_MAXVAL && $x < 3_000_000;
+ # Give an exact answer for what we have in our little table.
+ return _tiny_prime_count($x) if $x < $_primes_small[-1];
- $x = _upgrade_to_float($x) if ref($_[0]) eq 'Math::BigInt';
+ $x = _upgrade_to_float($x)
+ if ref($x) eq 'Math::BigInt' || ref($_[0]) eq 'Math::BigInt';
my $flogx = log($x);
@@ -2255,9 +2266,13 @@ sub prime_count_upper {
my($x) = @_;
_validate_num($x) || _validate_positive_integer($x);
- return $_prime_count_small[$x] if $x <= $#_prime_count_small;
+ # With XS using 30k tables, this is super fast.
+ return _XS_prime_count(2,$x) if $x < $_XS_MAXVAL && $x < 3_000_000;
+ # Give an exact answer for what we have in our little table.
+ return _tiny_prime_count($x) if $x < $_primes_small[-1];
- $x = _upgrade_to_float($x) if ref($_[0]) eq 'Math::BigInt';
+ $x = _upgrade_to_float($x)
+ if ref($x) eq 'Math::BigInt' || ref($_[0]) eq 'Math::BigInt';
# Chebyshev: 1.25506*x/logx x >= 17
# Rosser & Schoenfeld: x/(logx-3/2) x >= 67
@@ -2312,7 +2327,6 @@ sub prime_count_upper {
#else { $a = 2.51; } # Dusart 1999, page 14
# Old versions of Math::BigFloat will do the Wrong Thing with this.
- #return int( ($x/$flogx) * (1.0 + 1.0/$flogx + $a/($flogx*$flogx)) + 1.0 );
$result = ($x/$flogx) * (1.0 + 1.0/$flogx + $a/($flogx*$flogx)) + 1.0;
}
--
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
