tag:blogger.com,1999:blog-1806360094658697411.post4728624078059707982..comments2022-12-04T08:59:01.682-05:00Comments on The Lowly Programmer: Primes part 2: A segmented sieveEric Burnetthttp://www.blogger.com/profile/10741882872804697111noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1806360094658697411.post-35201150774328804402013-12-13T05:15:04.036-05:002013-12-13T05:15:04.036-05:00Eric, a great first post introducing the principle...Eric, a great first post introducing the principles of prime sieving using the Sieve of Eratosthenes and the logical progression of improved performance with gradually improved algorithms along with this follow-up post, but I think you stopped too soon in not considering further improvements to the Array based sieves as in paging, wheel factorization, and multi-threading, not to mention eliminating the enumeration itself for some types of results such as the count, the nth, and the sum of all elements over a range; when the other optimizations are fully utilized, enumeration takes about ten times longer than the process of actually culling composite numbers itself. Following is a link to a C# program that produces the count of the primes from the first four billion candidates (actually 2 ^ 32) in about a second on about the speed of machine as you likely were using to do these tests (fi7-2700K 3.5 GHz machine I was using), and even numerates them about five times faster than your Array based version: http://stackoverflow.com/a/18885065/549617. I'm not sure how to compute your "candidates per second" as this algorithm pre-culls some composite numbers using wheel factorization, but a range of four billion in one second might mean four billion candidates per second or it might mean 718 million candidates per second processed after pre-culling; alternatively it could mean about 515 million composite numbers eliminated per second leaving about 200 million primes. All of them are much faster than any C# prime sieving code I have seen published and only slower than extremely optimized C code.try2bGoodhttps://www.blogger.com/profile/12342631770782514910noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-70180426401601941752012-09-01T12:12:02.126-04:002012-09-01T12:12:02.126-04:00Thanks for the link! The paper your approach is ba...Thanks for the link! The paper your approach is based on was the basis for my original post (linked above), albeit not in Go. Definitely an interesting read (and fun to port to non-Haskell).<br /><br />> Interesting that your parallel segment filtering design will output primes but not in increasing order [...]<br /><br />It actually does output them in order. Segments are computed in parallel, but writing results to their own buffer channels. The contents of the buffers are later copied to the main output channel in segment order - there is a goroutine specifically dedicated to doing so. This somewhat limits the parallelism achievable (to 1.85x on my machine) since it involves non-trivial serial work, but it also means that all primes are output sequentially.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-87428645085145276772012-09-01T06:36:02.462-04:002012-09-01T06:36:02.462-04:00I also wrote an Eratosthenesque prime sieve using ...I also wrote an Eratosthenesque prime sieve using Go and channels here a while ago: http://blog.onideas.ws/eratosthenes.go<br /><br />It is slower than yours but is more channel-ish, i.e. lots of communicating over channels.<br /><br />Interesting that your parallel segment filtering design will output primes but not in increasing order, e.g. hard to ask "which is the 10 millionth prime?", but good for summing them I guess.Trinh Hai-Anhhttps://www.blogger.com/profile/15497739743932940838noreply@blogger.com