Thanks for writing this up. We talked about this a year ago! Brings back memories. I haven't made any sieve changes since your testing pointed out some inefficiencies and I did a release (June 13 2014). I just reran my benchmarks since I had a slightly older version of your sieve (before you added prefill and a few other things).

Here is a table of counting times for some segmented sieves. Single thread on i4770k.

Segmented sieves	10^9	10^10	10^11	10^12	10^13
yafu	0.285	1.876	20.241	4m 27.8s	54m 51s
primesieve 5.4.2	0.119	1.661	23.480	4m 56.0s	58m 18s
primegen 0.97	0.258	2.750	33.843	9m 43.1s	207m 56s
MPU 0.41	0.320	3.529	42.971	9m 28.8s	119m 3s
TOeS v2	0.422	4.739	55.283	10m 41.7s	121m 3s
Roy algo3 v2	0.435	5.087	64.456	12m 28.0s	150m 10s
Flammenkamp	0.528	5.937	79.211	16m 24.1s
tverniquet	0.643	6.937	80.876	17m 27.7s
Roy algo3 v1	0.611	6.949	77.846
Walisch bit segmnt	0.909	8.226	91.691	19m 9.9s

Comments: These all easily beat monolithic sieves such as Pari, Mathisen 1998, trivial SoE, MPU's plain sieve, etc. because I'm starting out at 10^9. All things are not equal: the code for counting is non-negligible and differs for most implementations. primegen is extremely sensitive to the cache parameter, which will differ on each platform. I tuned to the fastest value for this machine. The TOeS code also has some parameters I tuned but they're not as sensitive. Primesieve is set up for multiple threads -- this only uses one for direct comparison. Performance for primes from 2 to n may be very different than performance for primes from A to B (e.g. 10^18 to 10^18+1e6). This is purely for timing the sieves -- there are far faster ways to count primes (under a half-second for 10^13).

I don't benchmark printing primes because it becomes a contest of who can do the fastest itoa + write. That's nice, but the prime generation time gets lost. primesieve is faster generating primes, but with a good output routine I can beat it in printing by over 2x.

Random thoughts on this... yafu is quite fast, but the code isn't very usable outside of yafu. primesieve is extraordinarily fast, and would be faster if I let it use 8 threads. primegen is Bernstein's Sieve of Atkin which is pretty fast, but has poor growth compared to SoE (!) so my code catches it sometime before 10^12. Oliveira e Silva's example sieve is ok at smaller sizes but the growth rate is very nice so it's doing well at the high range (which was exactly what it was designed for). Algorithm 3 is doing very well, beating Flammenkamp's 2.0c code which used to be touted as one of the fastest sieves. Walisch's bit segment code is just an example of showing the idea and isn't optimized.

Thank you for this beautiful writeup danaj. I had spent many weeks converting Algorithm3 to a segmented sieve and was all I could do at the time. The best part of the experience was when I searched CPAN and came across Math::Prime::Util. Because, that is closer in reaching the powerful primesieve generator.

Thanks for this write-up. It's interesting. I hope that danaj has a chance to see it too.

Again, thanks for writing this up. Perl is indeed fun. MCE + Inline::C is pretty cool.

As I mentioned last year, counting primes can be much faster than sieving them. Using MCE with MPU's prime_count is counter-productive as it is doing much more work than a single thread calling it once. The analagous thing for primesieve is Kim Walisch's primecount -- also vastly faster than primesieve for counting. It's very slightly slower than MPU on a single thread, but its target is multiple threads where it cleans up. Times are on my MBP 2.2GHz (should be very similar to yours, just clocked lower). The only change is using the github version of Math::Prime::Util and changing bin/primeutil.pl to use the two new functions.

perl bin/algorithm3.pl 1_000_000_000
Prime numbers : 50847534
Compute time  : 0.163 sec

perl bin/primesieve.pl 1_000_000_000
Prime numbers : 50847534
Compute time  : 0.071 sec

perl bin/primeutil.pl 1_000_000_000
Prime numbers : 50847534
Compute time  : 0.025 sec

perl -Mntheory=:all -E 'say prime_count(1e9)'
50847534
0.020s user time
[download]

I added a simple sum_primes and print_primes yesterday. Not on CPAN yet. It helps quite a bit:

perl bin/algorithm3.pl 4_294_967_296 --sum
Sum of primes : 425649736193687430
Compute time  : 1.222 sec

perl bin/primesieve.pl 4_294_967_296 --sum
Sum of primes : 425649736193687430
Compute time  : 0.431 sec

perl bin/primeutil.pl 4_294_967_296 --sum
Sum of primes : 425649736193687430
Compute time  : 0.873 sec

perl -Mntheory=:all -E 'say sum_primes(2**32)'
425649736193687430
4.627s user time

perl -Mntheory=:all -E 'my $s=0; forprimes { $s+=$_ } 2**32; say $s'
425649736193687430
11.198s user time
[download]

The downside is that it a very specialized function, while forprimes { ... } $low,$high is very generic. There is also vecsum over primes, but that has even more overhead.

perl bin/algorithm3.pl 4_294_967_296 --print >/dev/null
Compute time  : 3.279 sec

perl bin/primesieve.pl 4_294_967_296 --print >/dev/null
Compute time  : 3.126 sec

perl bin/primeutil.pl 4_294_967_296 --print >/dev/null
Compute time  : 3.279 sec

perl -Mntheory=:all -E 'print_primes(2**32)' >/dev/null
8.149 user time

perl -Mntheory=:all -E 'forprimes { say } 2**32'
80.9s user time

primesieve -p1 2**32 >/dev/null
172.9s user time
[download]

Printing is much faster. Your code was better than the simple forprimes here of course, but now it will quickly print primes in a range to a file descriptor. It looks like our print timing is different -- maybe a difference in the temp file speed. primesieve's print time is excessive on this machine. I rebuilt it with a printf unsigned long and it went down to 28 seconds. It didn't change the MCE time since you're doing your own efficient printing.

One of these days I'll invert my code: rip out all the C code and put it in a standalone library for use by anything, then have ntheory (MPU) link to it. Then the MCE + Inline::C could get the high performance without mucking with XS.

Wow danaj. ++ for the sum_primes and print_primes functions. The sandbox was a lot of fun combining Perl + MCE + Inline::C. Generating primes made it more interesting.

Algorithm3 packs the sieve more tightly than regular odds-only (ie. in wheel6 formation, 2 bits per 6 numbers). Other than that, it's pretty much straight-up Eratosthenes. The clever flip-flops (k = 3 - k and ij = t - ij) disappear when the loops are unrolled (by hand or by compiler).

All in all, I don't expect this algorithm to hold much interest.

Using a mod-6 wheel is quite common. ntheory (aka Math::Prime::Util) uses a mod-30 wheel which is nice because their are 8 candidates per block, which packs nicely in a byte. The Sieve of Atkin is a twist on mod-30 (among other things, it's mod-60 which lets it skip 2,3,5). Terje Mathisen wrote a neat little monolithic mod-30 sieve in 1998 you can find on the net. I've seen a mod-2310 sieve but it seems very unwieldy for very little gain. PrimeSieve has 3 sieves for use at different sizes. A mod-30 sieve for small sizes, a mod-210 wheel for medium, and an optimized version of Oliveira e Silva's sieve for large sizes.

Quesada and Van Pelt wrote about a mod-30 sieve in 1996 (they cite Luo's 1989 paper), Sorenson in 1991. He even has a section discussing their agreements and disagreements with Luo's paper as well a Pritchard's earlier paper. Sorenson has a paper on Arxiv from March 2015 that I've been meaning to look at, though I don't think it will change anything (e.g. "The proof is a bit artificial and of theoretical interest only. Coding this in practice seems daunting."). People are still working on these things.

There is no question that primesieve is fast. It's great stuff, and Kim is a sharp developer who has been working on this for many years. He also has a slightly different target -- at large sizes the TOeS algorithm uses a lot of memory. I have tried to keep memory use more constrained. This comes up a lot with tables and precalculation, where I really can't do too much, as most users will probably never even call whatever function I'm optimizing, and I get a lot of feedback about trying to keep the initial size down. primesieve, and its sister project primecount, strive to be fast and offer C and C++ APIs.

Hmm, I had never heard before about Xuedong Luo, nor about "Algorithm3".

But when I was in my first year in technical high school (first university year) in computer science, back in 1989-1990, I was given a homework assignment to implement a prime number algorithm in Pascal (I remember it was in Pascal, but it might have been in Basic or in C, the two other languages we had to work with at the time). My first implementation was just a standard Eratosthenes sieve just using odd numbers both for numbers to be examined and for candidate divisors (with a special case for 2, the only even number that is prime).

In that assignment, I then noticed that the algorithm was getting really slow when getting around the 1,000,000 mark (if I remember correctly the timing, hardware of the time was really not like today, especially with my budget PC then). So I offered at least two possible performance optimizations:

- discarding even numbers and multiples of 3;

- choosing possible divisors only among the primes found so far;

If I remember correctly, I obtained the maximum possible mark for that homework assignment.

But if the real advantage of Algorithm3 is just discarding not only odd numbers but also multiples of 3, then I could almost claim to be a co-discoverer (I am of course just joking, I've never published on that, and I am fairly sure some other people thought about that possibility before). But, still, same idea, same period. And I am almost sure that I still have that assignment paper copy in my archives, with the annotations from my professor at the time (at least I still had it very recently, I don't think I have thrown it away in between).

I might try to post the Pascal abridged source code tomorrow, if I remember.

That is awesome. I like Algorithm3 a lot. It is exciting to know that someone else attempted to make the sieve of Eratosthenes faster. Beautiful minds.

I applaud Xuedong Luo, Laurent_R, and others for taking the sieve of Eratosthenes and creating a faster and more compact algorithm.

Ooh, I clicked on the wrong reply link. I met to reply above to Laurent_R.

Dana added sum_primes and print_primes in the Math::Prime::Util v.0.51 release.

The OP post was updated with results taken from v0.51 for the primeutil.pl example.

Thank you Dana for Math::Prime::Util.

Kind regards, Mario