1
\$\begingroup\$

This is my Clojure code for finding prime numbers.

Note: this is an advanced version which starts eliminating from i*i with step i, instead of filtering all list against mod i == 0 (Sieve of Eratosthenes).

It has better asymptotic runtime: O(n log log n) instead of O(n log n) in typical examples of finding primes in Clojure.

What can be done better? Do I use some slow constructions? Can I make it more concise? Gain more performance? Format it better?

(defn primes [n]
  (let [mark (fn [i di v]
               (if (<= i (count v))
                 (recur (+ i di) di (assoc v (dec i) di))
                 v))
        step (fn [i ps v]
               (if (<= i (count v))
                 (if (= (v (dec i)) 1)
                   (recur (inc i) (conj ps i) (mark (* i i) i v))
                   (recur (inc i) ps v))
                 ps))]
(->> (repeat 1) (take n) vec (step 2 []))))

(defn -main
  [& args]
  (println (primes 50)))
\$\endgroup\$
  • \$\begingroup\$ it will be n log (log n) only if (assoc v (dec i) di) is O(1). \$\endgroup\$ – Will Ness Jul 25 '13 at 7:15
2
\$\begingroup\$

(non-Clojure-specific) Gain performance, sure. Use packed array of odds, where index i represents value 2i+1. Then you don't have to deal with evens, which are all non-prime a priori (except the 2 of course). Then you can increment by 2*p for a prime p to find its odd multiples twice faster.

For a non-marked index i, the prime p is p = 2*i+1, its square is p*p = (2i+1)(2i+1) = 4i^2 + 4i + 1 and its index is (p*p-1)/2 = 2i^2 + 2i = 2i(i+1) = (p-1)(i+1). For the value increment of 2*p, the index increment on 2x-packed array is di = p = 2i+1.

\$\endgroup\$
1
\$\begingroup\$

I've played around with your code to try to understand it, frankly. After a long sequence of changes, I ended up with the following:

(defn primes [n]
  (let [mark (fn [i di v]
               (reduce
                 (fn [w i] (assoc w i di))
                 v
                 (range i (count v) di)))
        [answer &_] (reduce
                      (fn [[ps v :as both] i]
                        (if (= (v i) 1)
                          [(conj ps i) (mark (* i i) i v)]
                          both))
                      (let [init-v (->> (repeat 1) (take n) (vec))]
                        [[] init-v])
                      (range 2 n))]
    answer))
  • I've got rid of the decs in all the accesses to the vector v.
  • I've captured the recurs, in the mark and step functions, in reduces.
  • Since the step function is no longer recursive, I've unwrapped it into its one call.

The new mark function is a little faster. But the step equivalent is going to be slower, since it generates a new pair-vector for every prime.

The main problem here is space - your vector v is the size of your candidate range of numbers. I've come across a cute algorithm that gets round this, though at some cost in speed, spent on laziness.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.