开发者

A better concurrent prime number sieve in go

开发者 https://www.devze.com 2023-02-09 01:54 出处:网络
After looking at the prime number sieve code, and seeing how the concurrent structure works, I found it to be extremely elegant.

After looking at the prime number sieve code, and seeing how the concurrent structure works, I found it to be extremely elegant. However, it's also extremely inefficient, and IIRC, equivalent to the O(n^2) operation of testing the divisibility of the number m by dividing it by every number less than m. I figure that I开发者_运维问答 could instead modify it to use the O(n^1.5) operation of checking the divisibility of m by dividing it by every number less than or equal to the sqrt(m). However, this turned out to be a lot harder than I anticipated.

I know this is more of an algorithmics question, but it's also one extremely relevant to concurrency. How would one implement the O(n^1.5) version of the algorithm?


One place to look is stackoverflow, for example, the question Concurrent Prime Generator. Amongst the answers is one that uses Go and channels.


Elegant but inefficient prime sieve implementations are already well known to the Functional Programming community. This paper by Melissa O’Neill gives a good overview of lazy "stream" prime sieves as well as presenting efficient alternatives. (It uses Haskell, but should be a good read anyway)


Eratosthenes' sieve identifies prime p_i at iteration i and prunes all multiples of p_i from consideration in successive iterations. Given that, the only thing you can parallelise here is the pruning operation. This can only be sped up by a constant factor, so you won't change the big-O of the algorithm this way.

0

精彩评论

暂无评论...
验证码 换一张
取 消