Here's a slightly unconventional implementation which uses logical time to synchronize threads.

{- publish primes < n -}
def primes(n) =
  {- publish every dth number from i to n, one per
     unit of logical time -}
  def walk(i, d) =
    if i >= n then stop
    else Ltimer(1) >> (i | walk(i+d, d))
  {- visited non-prime numbers -}
  val seen = Set()
  2 | walk(3, 2) >i> if(~seen(i)?) >> (
    i | walk(i*i, i) >j> seen.add(j) >> stop
  )

primes(1000)

The algorithm is described in Tasking solutions to the Sieve of Eratosthenes. The idea is for one process to walk down the numbers and when it finds a prime number, it reports it and then sends another process forward to mark all multiples of that number as non-prime.

This implementation uses logical time to ensure that the prime-finding process moves more slowly than the prime-removing processes, so any number it visits has already been considered by all the prime-removing processes.

The work complexity is the same as the original Sieve of Eratosthenes: O(n log log n). The time complexity is O(n), since the prime-finding process does not take more than n/2 logical time steps to report all the primes, and each process is independent within each logical time step.

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-1) was last changed on 23-Mar-2009 12:09 by AdrianQuark