1
\$\begingroup\$

I ask because it seems to be taking waaaay more space/time than it should. Also, I know that if I want to be super efficient I should use Java's BitSet and a Sieve of Eratosthenes, but I wrote it like this to compare to a friend's implementation in C#.

(defn primes-upto [n]
  (let [primes (transient [2 3])]
    (loop [i 5]
      (if (> i n)
        (persistent! primes)
        (do (when
                (loop [j 0 is-prime true]
                  (let [p (primes j)]
                    (when is-prime
                      (if (> (* p p) i)
                        true
                        (recur (inc j) (not= 0 (mod i p)))))))
              (conj! primes i))
            (recur (+ i 2)))))))
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I get (primes-upto 100000) taking about 40 ms. I can't make it go much faster, but I can make it reliable. At present, it isn't.

The program works:

(primes-upto 10) ;[2 3 5 7]

But if you take away the transients, it fails:

(defn primes-upto [n]
  (let [primes [2 3]]
    (loop [i 5]
      (if (> i n)
        primes
        (do (when
              (loop [j 0, is-prime true]
                (let [p (primes j)]
                  (when is-prime
                    (or (> (* p p) i)
                        (recur (inc j) (not= 0 (mod i p)))))))
              (conj primes i))
          (recur (+ i 2)))))))

(primes-upto 10); java.lang.IndexOutOfBoundsException: null ...

The program is depending upon accidents of how transients are implemented. Transients don't promise to update their bindings. They revoke the promise of immutability.

Rewriting the program idiomatically, I get ...

(defn primes-upto [n]
  (loop [primes [2 3], i 5]
    (if (> i n)
      primes
      (let [i-prime? (loop [j 1]
                       (let [p (long (primes j))]
                         (or (> (* p p) i)
                             (and (not= 0 (mod i p))
                                  (recur (inc j))))))]
        (recur (if i-prime? (conj primes i) primes) (+ i 2))))))

... including a few variations:

  • The inner loop is simpler, and employs and and or for brevity.
  • Since we increment i by 2, we don't need to check for division by 2, so start with j at 1.
  • Convert p to a long explicitly, to help with type inference.
  • Dispense with transients.

When all's said and done, it's a little faster, but not much. Transients don't help much either.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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