My cousin was solving a programming challenge involving the collatz conjecture. He was implementing his solution using dynamic programming in C++

I thought it would be fun to try and write it in Clojure.

Our solutions are pretty similar, and mine ended up being about 2 times slower than his.

(set! *warn-on-reflection* true)
(defn check-len*
([l cache] (check-len* l cache 1))
([k cache len]
(loop [k (long k)
len (long len)]
(let [val (get cache k)
is-even (even? k)]
(if val
(unchecked-dec (unchecked-add len (long val)))
(if (== k (long 1)) len
(recur (long (if is-even
(bit-shift-right (long k) (long 1))
(unchecked-add (long k)
(unchecked-add (long 1)
(long (bit-shift-right k 1))))))
(long (if is-even
(unchecked-inc len)
(unchecked-add len (long 2)))))))))))
(defn check-max [a b]
(loop [i (long a)
max (long 0)
cache {}]
(if (>= i b) max
(let [val (check-len* i cache)]
(recur (inc i)
(long (if (> val max) val max))
(assoc cache i val))))))
(defn go [beg end]
(time (check-max beg end)))

As of memory, for the range 1-10,000,000 I am using 1.7gb of heap memory, while the C++ implementation is using 1.2gb.

My implementation is 42% beefier. and 2x slower. But it’s smaller!

Since almost half the time is spent putting and getting values from the clojure map, using a Java HashMap is an improvement, and actually makes the solution faster than the C++ version. (Memory-wise, it settles on less than 1.2gb after the solution, but just before it finishes it reaches 1.4gb)

(set! *warn-on-reflection* true)
(import '(java.util HashMap))
(defn check-len*
([l #^HashMap cache] (check-len* l cache 1))
([k #^HashMap cache len]
(loop [k (long k)
len (long len)]
(let [val (. cache get k)
is-even (even? k)]
(if val
(unchecked-dec (unchecked-add len (long val)))
(if (== k (long 1)) len
(recur (long (if is-even
(bit-shift-right (long k) (long 1))
(unchecked-add (long k)
unchecked-add (long 1)
(long (bit-shift-right k 1))))))
(long (if is-even
(unchecked-inc len)
(unchecked-add len (long 2)))))))))))
(defn check-max [a b]
(loop [i (long a)
max (long 0)
cache (new HashMap)]
(if (>= i b) max
(let [val (check-len* i cache)]
(. cache put i val)
(recur (inc i)
(long (if (> val max) val max))
cache)))))
(defn go [beg end]
(time (check-max beg end)))

An all-around better solution is to use the optimization tips on the wikipedia article for the Collatz Conjecture, which would reduce it to some arithmetic trickery.

### Like this:

Like Loading...

*Related*