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

## 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?

(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.

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.

• Unchecked maths looks safe here. Even if it wasn't, It is what the Java does. Jul 25 '16 at 9:49