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 3fedfb5a333ccc63b4315ee96c60bf87f79b3edf Author: Dana Jacobsen <d...@acm.org> Date: Wed Jun 27 03:12:05 2012 -0600 Add simple SoA (along with rant) --- examples/bench-sieve-pp.pl | 96 +++++++++++++++++++++++++++++++++++++++++----- lib/Math/Prime/Util.pm | 1 + 2 files changed, 87 insertions(+), 10 deletions(-) diff --git a/examples/bench-sieve-pp.pl b/examples/bench-sieve-pp.pl index 724351b..45e3151 100644 --- a/examples/bench-sieve-pp.pl +++ b/examples/bench-sieve-pp.pl @@ -13,21 +13,24 @@ my $upper = shift || 8192; my $count = shift || -1; my $countarg; +#atkin2(100); exit(0); + # Shows sizes for sieving to 100k, and rate/second for sieving to 16k my $pc_subs = { - "Scriptol" => sub { scriptol($countarg) }, # 3200k 290/s - "Shootout" => sub { shootout($countarg) }, # 3200k 231/s - "In Many" => sub { inmany($countarg) }, # 2018k 666/s - "Rosetta 1" => sub { rosetta1($countarg) }, # 3449k 187/s - "Rosetta 2" => sub { rosetta2($countarg) }, # 13k 109/s - "Rosetta 3" => sub { rosetta3($countarg) }, # 4496k 165/s "Rosetta 4" => sub { rosetta4($countarg) }, # 25k 60/s "Atkin MPTA" => sub { atkin($countarg) }, # 3430k 90/s - "DO Array" => sub {daoswald_array($countarg)},# 3200k 306/s - "DO Vec" => sub {daoswald_vec($countarg)}, # 13k 112/s "Merlyn" => sub { merlyn($countarg)}, # 13k 96/s + "Rosetta 2" => sub { rosetta2($countarg) }, # 13k 109/s + "Atkin 2" => sub { atkin2($countarg) }, # 1669k 110/s + "DO Vec" => sub {daoswald_vec($countarg)}, # 13k 112/s + "Rosetta 3" => sub { rosetta3($countarg) }, # 4496k 165/s + "Rosetta 1" => sub { rosetta1($countarg) }, # 3449k 187/s + "Shootout" => sub { shootout($countarg) }, # 3200k 231/s "DJ Vec" => sub { dj1($countarg) }, # 7k 245/s + "Scriptol" => sub { scriptol($countarg) }, # 3200k 290/s + "DO Array" => sub {daoswald_array($countarg)},# 3200k 306/s "DJ Array" => sub { dj2($countarg) }, # 1494k 475/s + "In Many" => sub { inmany($countarg) }, # 2018k 666/s "DJ String1" => sub { dj3($countarg) }, # 50k 981/s "DJ String2" => sub { dj4($countarg) }, # 50k 1682/s # "MPU Sieve" => sub { @@ -256,11 +259,84 @@ sub atkin { $count; } +# Naive Sieve of Atkin, basically straight from Wikipedia. +# +# <rant> +# +# First thing to note about SoA, is that people love to quote things like +# "memory use is O(N^(1/2+o(1)))" then proceed to _clearly_ use N bytes in +# their implementation. If your data structures between SoA and SoE are the +# same, then all talk about comparative O(blah..blah) memory use is stupid. +# +# Secondly, assuming you're not Dan Bernstein, if your Sieve of Atkin is +# faster than your Sieve of Eratosthenes, then I strongly suggest you verify +# your code actually _works_, and secondly I would bet you made stupid mistakes +# in your SoE implementation. If your SoA code even remotely resembles the +# Wikipedia code and it comes out faster than SoE, then I _guarantee_ your +# SoE is borked. +# +# SoA does have a slightly better asymptotic operation count O(N/loglogN) vs. +# O(N) for SoE. The Wikipedia-like code that most people use is O(N) so it +# isn't even theoretically better unless you pull lots of stunts like primegen +# does. Even if you do, loglogN is essentially a small constant for most uses +# (it's under 4 for all 64-bit values), so you need to make sure all the rest +# of your overhead is controlled. +# +# Sumarizing, in practice the SoE is faster, and often a LOT faster. +# +# </rant> +# +sub atkin2 { + my($max) = @_; + return 0 if $max < 2; + return 1 if $max < 3; + + my @sieve; + + my $sqrt = int(sqrt($max)); + for my $x (1 .. $sqrt) { + for my $y (1 .. $sqrt) { + my $n; + + $n = 4*$x*$x + $y*$y; + if ( ($n <= $max) && ( (($n%12) == 1) || (($n%12) == 5) ) ) { + $sieve[$n] ^= 1; + } + $n = 3*$x*$x + $y*$y; + if ( ($n <= $max) && (($n%12) == 7) ) { + $sieve[$n] ^= 1; + } + $n = 3*$x*$x - $y*$y; + if ( ($x > $y) && ($n <= $max) && (($n%12) == 11) ) { + $sieve[$n] ^= 1; + } + } + } + + for my $n (5 .. $sqrt) { + if ($sieve[$n]) { + my $k = $n*$n; + my $z = $k; + while ($z <= $max) { + $sieve[$z] = 0; + $z += $k; + } + } + } + $sieve[2] = 1; + $sieve[3] = 1; + #print "Atkin size: ", total_size(\@sieve), "\n" if $max > 90000; + + my $count = scalar grep { $sieve[$_] } 2 .. $#sieve; + $count; +} + # https://github.com/daoswald/Inline-C-Perl-Mongers-Talk/blob/master/primesbench.pl sub daoswald_array { my($top) = @_; return 0 if $top < 2; return 1 if $top < 3; + $top++; my @primes = (1) x $top; my $i_times_j; @@ -286,13 +362,13 @@ sub daoswald_vec { my $i_times_j; for my $i ( 2 .. sqrt $top ) { if ( !vec( $primes, $i, 1 ) ) { - for ( my $j = $i; ( $i_times_j = $i * $j ) < $top; $j++ ) { + for ( my $j = $i; ( $i_times_j = $i * $j ) <= $top; $j++ ) { vec( $primes, $i_times_j, 1 ) = 1; } } } #print "do_vec size: ", total_size(\$primes), "\n" if $top > 90000; - my $count = scalar grep { !vec( $primes, $_, 1 ) } 2 .. $top-1 ; + my $count = scalar grep { !vec( $primes, $_, 1 ) } 2 .. $top ; $count; } diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 6b66cc7..1937264 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -825,6 +825,7 @@ Pi(10^10) = 455,052,511. 2.2 yafu 1.31 3.8 primegen (optimized Sieve of Atkin, conf-word 8192) 5.6 Tomás Oliveira e Silva's unoptimized segmented sieve v2 (Sep 2010) + 6.7 Achim Flammenkamp's prime_sieve (32k segments) 9.3 http://tverniquet.com/prime/ (mod 2310, single thread) 11.2 Tomás Oliveira e Silva's unoptimized segmented sieve v1 (May 2003) 17.0 Pari 2.3.5 (primepi) -- 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