Here is a golang version of Daniel Bernstein's "eratspeed", which is a straight translation of his C code to golang without any changes other than as necessary to make it work: https://play.golang.org/p/Sd6qlMQcHF.

It won't run on the golang playground because it takes too long unless one changes the number of loops it runs, but at least one gets a nicely formatted listing.

I haven't played with optimizing this other than to turn of array bounds checks in compiling it (to make it more comparable to C), but it seems that "as-is" it runs at about the same speed as John's "primespeed" code from the beginning of this thread when that code has multi-threading disabled (force numprocs = 1 in the sieve.go file) when both have array bounds checking turned off, and both for these conditions run slightly faster than Bernstein's C "primespeed" in 32-bit mode just as compiled with GCC using his "make". Bernstein's C "eratspeed" under those some conditions runs about 17% slower than his "primespeed", which makes it about 20% slower than this golang version. Those are all under the conditions of being compiled and run on my machine, which isn't particularly fast of efficient.

Neither have I yet looked at the machine code generated by this version of eratspeed, but it is likely helped by there being more constants so there is less of a demand for registers.

This isn't the ultimate in Sieve of Eratosthenes algorithms yet as it could be maximally factorized (use a 2/3/5/7 wheel instead of the 2/3/5 one used and use a pre-cull pattern which has the 11/13/17/19 prime composites eliminated to initialize the culling array) to save about another 25% to 30%, multi-threading could be applied for another speed up by a factor of four on 4 cores plus HT CPU's; it also needs some work to make the range extendable since, as it is currently written, it is hard coded to sieve up to this specific range.

Anyway, compare apples with apples, both algorithms true to those written by Bernstein.

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

Discussion Posts


Follow ups

Related Discussions

Discussion Navigation
viewthread | post
posts ‹ prev | 25 of 27 | next ›
Discussion Overview
groupgolang-nuts @
postedJun 14, '16 at 12:31p
activeJun 18, '16 at 10:54a



site design / logo © 2021 Grokbase