Chain call in clojure?

Question

I'm trying to implement sieve of Eratosthenes in Clojure. One approach I would like to test is this:

1. Get range (2 3 4 5 6 ... N)
2. For 2 <= i <= N
   • Pass my range through filter that removes multiplies of i
   • For i+1th iteration, use result of the previous filtering

I know I could do it with loop/recur, but this is causing stack overflow errors (for some reason tail call optimization is not applied).

How can I do it iteratively? I mean invoking N calls to the same routine, passing result of ith iteration to i+1th.

Answer 1

(defn sieve [beg end]
  (letfn [(siever [to-sieve sieved]
                  (if (empty? to-sieve) sieved
                  (let [[f & r] to-sieve]
                    (if (> f (Math/sqrt end)) (into sieved to-sieve)
                        (recur (remove #(zero? (mod % f)) r) 
                           (conj sieved f))))))]
    (siever (range beg (inc end)) [])))

This one seems to work just fine. Tested it with (sieve 2 1000000) and returns within seconds without blowing.

Answer 2

Oh, I've already posted a comment on your other question before seeing this one... At any rate, the Sieve of Eratosthenes performs no remainder / modulo calculations, only addition (to move across a list in increments of p, where p is the last prime to be discovered so far) and "crossing out". Of course the results produced by a "remainder + filter" sieve are the same as those produced by SoE, but the algorithmic complexity of the two sieving schemes is completely different.

Now, a strictly faithful SoE needs to be "finite", in that it can only operate on a fixed-length array of numbers; however the basic algorithm can be modified to support "incremental" sieving -- with lazy generation of an arbitrary number of primes -- if an additional data structure is kept around to record information of which numbers where reached the "crossing out" passes for each of the primes found so far. The perfect choice for such a data structure would be a priority queue, however a map is very usable as well.

For an extended discussion of incremental sieving in functional languages based on this idea -- including a careful analysis of the complexity of all the algorithms involved -- see Melissa E. O'Neill's article The Genuine Sieve of Eratosthenes. It uses Haskell, but that shouldn't be a problem (no esoteric features are being used and the Haskell code is especially clear, so it reads pretty much like regular mathematical notation).

For example implementations in Clojure, see Christophe Grand's Everybody loves the Sieve of Eratosthenes blog entry -- highly recommended, the final version is absolutely beautiful and very fast -- and maybe a couple of my Gists, if I may take the liberty of plugging them here: the first one, the second one. (Note that these aren't very pretty at all, but they were useful as an experiment to me... The second one uses a priority queue in contrast to the others, which are map-based, so hopefully it'll be useful as a crude illustration now.)

I guess I'm not answering your main Clojure implementation question, but I reckon between Michiel's answer and the leading answer to your other question, that one is already solved.