This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.40 in repository libmath-prime-util-perl.
commit 2caa6e5709c03674694305a465d7e2104593cac7 Author: Dana Jacobsen <d...@acm.org> Date: Fri Mar 28 12:43:41 2014 -0700 Small nth_twin_prime speedup. xt test for twin_prime_count --- MANIFEST | 1 + util.c | 14 +++++----- xt/twin_prime_count.t | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 84 insertions(+), 7 deletions(-) diff --git a/MANIFEST b/MANIFEST index 554f354..31a067d 100644 --- a/MANIFEST +++ b/MANIFEST @@ -145,4 +145,5 @@ xt/test-primes-script2.pl xt/test-factor-yafu.pl xt/test-nextprime-yafu.pl xt/test-ispower.pl +xt/twin_prime_count.t .travis.yml diff --git a/util.c b/util.c index 771c52a..6a46b47 100644 --- a/util.c +++ b/util.c @@ -966,14 +966,14 @@ UV nth_twin_prime(UV n) void* ctx = start_segment_primes(beg, end, &segment); while (next_segment_primes(ctx, &seg_base, &seg_low, &seg_high)) { UV p, bytes = (seg_high-seg_low+29)/30; + UV s = ((UV)segment[0]) << 8; for (p = 0; p < bytes; p++) { - UV s = segment[p]; - int twin1 = !(s & 0x0C); - int twin2 = !(s & 0x30); - int twin3 = !(s & 0x80) && ((p+1 < bytes) ? !(segment[p+1] & 0x01) : _XS_is_prime(seg_high+2)); - if (twin1 && !--n) { nth=seg_base+p*30+11; break; } - if (twin2 && !--n) { nth=seg_base+p*30+17; break; } - if (twin3 && !--n) { nth=seg_base+p*30+29; break; } + s >>= 8; + if (p+1 < bytes) s |= (((UV)segment[p+1]) << 8); + else if (!_XS_is_prime(seg_high+2)) s |= 0xFF00; + if (!(s & 0x000C) && !--n) { nth=seg_base+p*30+11; break; } + if (!(s & 0x0030) && !--n) { nth=seg_base+p*30+17; break; } + if (!(s & 0x0180) && !--n) { nth=seg_base+p*30+29; break; } } if (n == 0) break; } diff --git a/xt/twin_prime_count.t b/xt/twin_prime_count.t new file mode 100644 index 0000000..a7898a3 --- /dev/null +++ b/xt/twin_prime_count.t @@ -0,0 +1,76 @@ +#!/usr/bin/env perl +use strict; +use warnings; + +use Test::More; +use Math::Prime::Util qw/twin_prime_count/; + +# 2^n using primesieve (fast), double checked with Pari 2.7.0 (slow): +# a(n)=my(s, p=2); forprime(q=3, 2^n, if(q-p==2, s++); p=q); s +# for (i=1,35,print(2^i," ", a(i))) +# 10^n from tables +my %tpcvals = ( + 1 => 0, + 2 => 0, + 4 => 1, + 8 => 2, + 16 => 3, + 32 => 5, + 64 => 7, + 128 => 10, + 256 => 17, + 512 => 24, + 1024 => 36, + 2048 => 62, + 4096 => 107, + 8192 => 177, + 16384 => 290, + 32768 => 505, + 65536 => 860, + 131072 => 1526, + 262144 => 2679, + 524288 => 4750, + 1048576 => 8535, + 2097152 => 15500, + 4194304 => 27995, + 8388608 => 50638, + 16777216 => 92246, + 33554432 => 168617, + 67108864 => 309561, + 134217728 => 571313, + 268435456 => 1056281, + 536870912 => 1961080, + 1073741824 => 3650557, + 2147483648 => 6810670, + 4294967296 => 12739574, + 8589934592 => 23878645, + 17179869184 => 44849427, + 34359738368 => 84384508, + 68719476736 => 159082253, +# 137438953472 => 300424743, + 10 => 2, + 100 => 8, + 1000 => 35, + 10000 => 205, + 100000 => 1224, + 1000000 => 8169, + 10000000 => 58980, + 100000000 => 440312, + 1000000000 => 3424506, + 10000000000 => 27412679, + 100000000000 => 224376048, + 1000000000000 => 1870585220, + 10000000000000 => 15834664872, + 100000000000000 => 135780321665, + 1000000000000000 => 1177209242304, + 10000000000000000 => 10304195697298, + 100000000000000000 => 90948839353159, + 1000000000000000000 => 808675888577436, +); + +plan tests => scalar(keys %tpcvals); + +foreach my $n (sort {$a <=> $b} keys %tpcvals) { + my $tpc = $tpcvals{$n}; + is( twin_prime_count($n), $tpc, "Pi_2($n) = $tpc" ); +} -- 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