Clojure performance for solving Project Euler 72 (counting proper reduced fractions)

Question

Challenge

This is a solution of Project Euler 72 in Java.

How may proper reduced fractions \$\dfrac{n}{d}\$ are there, where \$n < d \le 10^6\$?

Code

public long solve() {
  int limit = 1000000;
  int[] phi = IntStream.range(0, limit + 1).toArray();
  long result = 0;
  for (int i = 2; i <= limit; i++) {
    if (phi[i] == i) {
      for (int j = i; j <= limit; j += i) {
        phi[j] = phi[j] / i * (i - 1);
      }
    }
    result += phi[i];
  }
  return result;
}

The algorithm is explained in detail here. When I run the above code on my machine, it takes 150ms to get the answer.

I translated this code into Clojure like the below.

(defn solve []
  (let [limit 1000000
        phi (int-array (range (inc limit)))]
    (loop [i 2 acc 0]
      (if (= i (aget phi i))
        (loop [j i]
          (if (<= j limit)
            (do (aset phi j (/ (* (aget phi j) (dec i)) i))
                (recur (+ j i))))))
      (if (< i limit)
        (recur (inc i) (+ acc (aget phi i)))
        acc))))

This code uses Java array and mutate the value within the array. The algorithm is logically the same. However, when I run this code in repl, it takes over 25 seconds, which is a huge difference from the Java solution.

I expected that the Clojure code slightly slower than Java. But this is not a slight difference. Why is the Clojure code is slow like this. Did I miss something? Or is there other way to do this better?

Answer 1

(time (solve))

=> "Elapsed time: 27363.381633 msecs"

Replace aset with aset-int:

(defn solve []
  (let [limit 1000000
        phi (int-array (range (inc limit)))]
    (loop [i 2 acc 0]
      (if (= i (aget phi i))
        (loop [j i]
          (if (<= j limit)
            (do (aset-int phi j (/ (* (aget phi j) (dec i)) i))
              (recur (+ j i))))))
      (if (< i limit)
        (recur (inc i) (+ acc (aget phi i)))
        acc))))

(time (solve))

=> "Elapsed time: 443.570909 msecs"

This is still three times slower than the Java, but not out of sight.

I thought the original might be using type reflection, but ...

(set! *warn-on-reflection* true)

... produces no response to the original code.

Answer 2

As per this SO answer it's super useful to check the generated bytecode for the function as well.

Replacing / with quot gives a small speed-up as well.

There's also (set! *unchecked-math* true) but it's probably wise to be careful with that.