4
\$\begingroup\$

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?

\$\endgroup\$
0

2 Answers 2

4
+50
\$\begingroup\$
(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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Unchecked maths looks safe here. Even if it wasn't, It is what the Java does. \$\endgroup\$
    – Thumbnail
    Jul 25, 2016 at 9:49

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.