-
-
Save unclebob/632303 to your computer and use it in GitHub Desktop.
(ns prime-factors-test | |
(:use clojure.test midje.sweet)) | |
(defn factors-starting-at [f n] | |
(cond | |
(> f (Math/sqrt n)) (if (= n 1) [] [n]) | |
(= 0 (mod n f)) (cons f (factors-starting-at f (/ n f))) | |
:else (recur (inc f) n))) | |
(defn prime-factors-of [n] | |
(factors-starting-at 2 n)) | |
(defn mersenne [n] | |
(int (dec (Math/pow 2 n)))) | |
(deftest prime-factors | |
(fact (prime-factors-of 1) => []) | |
(fact (prime-factors-of 2) => [2]) | |
(fact (prime-factors-of 3) => [3]) | |
(fact (prime-factors-of 4) => [2 2]) | |
(fact (prime-factors-of 5) => [5]) | |
(fact (prime-factors-of 6) => [2 3]) | |
(fact (prime-factors-of 7) => [7]) | |
(fact (prime-factors-of 8) => [2 2 2]) | |
(fact (prime-factors-of 9) => [3 3]) | |
(fact (prime-factors-of 10) => [2 5]) | |
(fact (prime-factors-of 12) => [2 2 3]) | |
(fact (prime-factors-of 18) => [2 3 3]) | |
(fact (prime-factors-of 25) => [5 5]) | |
(fact (prime-factors-of 1369) => [37 37]) | |
(fact (prime-factors-of (* 2 3 5 7 11 17 37)) => [2 3 5 7 11 17 37]) | |
(fact (prime-factors-of (mersenne 17)) => [(mersenne 17)]) | |
(fact (prime-factors-of (mersenne 19)) => [(mersenne 19)]) | |
(fact (prime-factors-of (mersenne 31)) => [(mersenne 31)]) | |
) | |
(run-tests) |
Good point on the (zero?), I had forgotten about that.
I chose the non-tail version because it only pushes the stack for prime factors that are repeated. So it could blow the stack for n**b where b is very large; but for most numbers it's pretty safe.
In general, though, tail-recursion should be preferred (of course) despite the extra arg.
Hi @unclebob,
I was attempting a version that didn't require the call-out to factors-starting-at, but instead applied a default starting factor. I came up with the following:
(I'm not using (cond), which is way neater; instead what is below reflects the structure of your original PrimeFactors kata in java)
(defn prime-factors-of
([n] (prime-factors-of 2 n))
([f n]
(if (> n 1)
(if (= 0 (mod n f))
(cons f (prime-factors-of f (/ n f)))
(recur (inc f) n)
)
()
)
)
)
What is your opinion of the default value form versus extracting the factors-of function? I'm on the fence - SRP and clear names versus the simplicity of a single recursive call.
@hoodja: although it might seem strange when seen from a curly-brace-language-background, lispers like to put all closing parens on a single line (they feel lonely otherwise):
(defn prime-factors-of
([n] (prime-factors-of 2 n))
([f n]
(if (> n 1)
(if (= 0 (mod n f))
(cons f (prime-factors-of f (/ n f)))
(recur (inc f) n))
[])))
I replaced ()
by []
to make the empty list stand out more clearly from all those parens.
To repeat my comment from above: (zero? num)
is more readable than (= 0 num)
IMHO, and it also has performance benefits (nice combo).
@unclebob:
I think that you really need an extra (accumulator) argument to make the function tail-recursive. But I'd be delighted if you can prove me wrong!
I would use (zero? foo) instead of (= 0 foo). IMVHO it's more readable, and according to Rich Hickey it also performs better.
I would also be interested what you think about the non-stack-smashing version:
Does the extra argument hurt readability so bad that the non-tail-recursive version should be preferred for small numbers?