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.

• Thumbnail: Unchecked maths looks safe here. Even if it wasn't, It is what the Java does.