Clojure - tail recursive sieve of Eratosthenes

Question

I have this implementation of the sieve of Eratosthenes in Clojure:

(defn sieve [n]
  (loop [last-tried 2 sift (range 2 (inc n))]
    (if
      (or (nil? last-tried) (> last-tried n))
      sift
      (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
        (let [next-to-try (first (filter #(> % last-tried) filtered))]
        (recur next-to-try filtered))))))

For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?

As a side note, but this is not the sieve of Eratosthenes. SoE performs no remainder operations, just addition and "crossing out". See http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf for an extended discussion (it's a great read!); for a beautiful "incremental" SoE implementation in Clojure by Christophe Grand, see http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ (it's also the fastest version I've seen so far). — Michał Marczyk, Jun 05 '10 at 14:18
@Michał Marczyk thanks. I would say that "crossing out" is equivalent of "filtering", and "addition" in this algorithm is equivalent of "multiplication" and consequently "remainder". — Konrad Garus, Jun 05 '10 at 14:32
Not really. The result is, of course, the same, but the algorithmic complexity is wildly different. — Michał Marczyk, Jun 05 '10 at 14:33
the article is very good with math but unfortunately does poor job with words explaining the math. the difference is between iterative removal of composites tested by contiguous increasing chunks of primes *(first 1, first 2, first 3 primes, first 4 primes, ...)* , vs. independent production of composites each from *its prime factors only* ( `p --> {p*p, p*p+p, p*p+2*p, ...}` ). — Will Ness, Jan 12 '17 at 17:50

score 12 · Accepted Answer · edited Jun 20 '20 at 09:12

12

Problem: filter does lazy evaluation, so each new level of filtering hangs around on the call stack.

Fix: Change (filter ...) to (doall (filter ...)).

See the explanation here.

edited Jun 20 '20 at 09:12

Community

1
1

answered Jun 05 '10 at 14:05

j-g-faustus

8,801
4
32
42

score 2 · Answer 2 · answered Jun 05 '10 at 13:55

2

If you look at the backtrace

(try
 (sieve 200000)
 (catch java.lang.StackOverflowError e
  (.printStackTrace e)))

it looks like this:

...
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
at clojure.lang.RT.seq(RT.java:440)
at clojure.core$seq__4176.invoke(core.clj:103)
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751)
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
...

It's too many filters that's causing the overflow, not the loop.

Unfortunately, I don't see an obvious solution for this.

answered Jun 05 '10 at 13:55

cobbal

69,903
20
143
156

The clue was in the LazySeq. Clojures implementation of Laziness has a few gotchas this being one of them. – Jeremy Wall Jun 06 '10 at 04:40
you've correctly identified the main algorithmic problem (as opposed to just technical). an obvious solution is to stop filtering as soon as there's no more need to filter. and that is, when `(> (* last-tried last-tried) n)`. For 20000, that means trading recursion depth of roughly 2000, for just about 30. – Will Ness Jan 12 '17 at 17:36
(indeed [for 16,000](http://stackoverflow.com/a/41621006/849891) it's 30 vs 1862 nested filters). – Will Ness Jan 12 '17 at 19:19

score 0 · Answer 3 · answered Jun 09 '10 at 03:16

0

I second Michal Marczyk's comment about checking out cgrande's beautiful incremental SoE. I did some really primitive benchmarks and put them up at http://clojure.roboloco.net/?p=100, for those curious about lazy prime generator performance.

answered Jun 09 '10 at 03:16

ivar

1,484
12
20

Clojure - tail recursive sieve of Eratosthenes

3 Answers3

Linked