Learn A New Language
March 4, 2014
I chose to implement my modest prime-number library in Clojure. Clojure is similar to Scheme, which actually made things harder for me, not easier, because my fingers kept typing things all by themselves. Of course, that’s the point of the exercise, to break those habits and make you think about what you are doing. Here’s my library:
(defn gcd "greatest common divisor" [a b]
(if (zero? b) a (gcd b (mod a b))))
I was surprised not to find gcd in the base libraries of Clojure. This looks familiar, of course. I like the addition of doc strings; some Scheme systems provide them as a non-standard addition to the language, and they provide useful documentation.
(defn powerMod "modular exponentiation" [b e m]
(defn m* [p q] (mod (* p q) m))
(loop [b b, e e, x 1]
(if (zero? e) x
(if (even? e) (recur (m* b b) (/ e 2) x)
(recur (m* b b) (quot e 2) (m* b x))))))
Clojure permits internal function definitions, just like Scheme, so again there is nothing new here. I constantly had trouble with the parentheses that Clojure omits — my fingers type them automatically — and I made use of Clojure’s optional comma operator to separate the clauses of the let. I’m not sure I like the new syntax; it seems to me that it would be easy to mess up a complicated cond expression by mis-matching the clauses. I discovered during testing that Clojure seems to have no way to write powers of ten as big integer literals, analogous to Scheme’s #e1e40.
(defn primes "primes less than n" [n]
(let [sieve (boolean-array n true)]
(loop [p 2, ps (list)]
(cond (= n p) (reverse ps)
(aget sieve p)
(do (doseq [i (range (* p p) n p)]
(aset sieve i false))
(recur (+ p 1) (cons p ps)))
:else (recur (+ p 1) ps)))))
It didn’t take me long to realize that what Clojure calls vectors aren’t really vectors; instead, they are trees with 32-way branching, so lookup is O(log32 n) instead of O(1). That’s not a big difference, but it makes a huge difference. It took me longer to realize that what Clojure calls lists aren’t really lists, either; they’re just backwards vectors, there are no pairs as in Scheme, so no improper lists, and somehow Clojure keeps track of the length of a list because length is an O(1) operation. Clojure arrays, as used above, are what I expect them to be. The recur syntax performs a recursive call, and must be in tail position; I suppose that’s a reaction to the lack of tail call elimination in the JVM, but it will take some getting used to.
(defn prime? "miller-rabin primality test" [n]
(defn witness? [n a]
(loop [d (- n 1), s 0]
(if (even? d) (recur (/ d 2) (+ s 1))
(let [t (powerMod a d n)]
(if (= t 1) false ; probably prime
(loop [t t, s s]
(if (zero? s) true ; composite
(if (= t (- n 1)) false ; probably prime
(recur (powerMod t 2 n) (- s 1))))))))))
(if (= n 2) true
(loop [i 25] ; arbitrary number of witness trials
(if (zero? i) true ; probably prime
(let [a (+ 2 (rand-int (min 100000 (- n 2))))]
(if (witness? n a) false ; composite
(recur (- i 1))))))))
I normally implement this test using a witness list of the first twenty-five primes, but I couldn’t figure out a way to store that list in the function so that it didn’t have to be re-computed each time the function was called. So I switched to twenty-five random witnesses, and had trouble with that before I realized that rand-int is limited to the native integer size and doesn’t permit big integers. And one of the tests that I always use is 289−1, which is prime, but I couldn’t figure out a way to compute 289−1 because the powering operation uses floating point numbers instead of big integers.
(defn factors "pollard-rho factorization" [n]
(defn rho [n c]
(defn f [x] (mod (+ (* x x) c) n))
(loop [h 5, t 2, d 1]
(if (< 1 d) d
(recur (f (f h)) (f t) (gcd (- t h) n)))))
(if (<= -1 n 1) (list n)
(if (neg? n) (cons -1 (factors (- n)))
(loop [n n, c 1, fs (list)]
(if (= n 1) fs (if (prime? n) (sort < (cons n fs))
(if (even? n) (recur (/ n 2) c (cons 2 fs))
(let [d (rho n c)]
(if (prime? d)
(recur (/ n d) (+ c 1) (cons d fs))
(recur n (+ c 1) fs))))))))))
I was pleased to see that Clojure provides sort as a built-in; some Scheme systems don’t, including the Scheme at codepad.org that I use for all my sample code. I was less pleased, though, that Clojure seems to provide no way to have two nested loops, analogous to Scheme’s named-let, instead using the recur syntax to provide only a single level of looping. I solved that problem by splitting the rho loop into a separate function, but that seems awkward to me, and harms readability.
You can see the code assembled at http://programmingpraxis.codepad.org/SpVF5kd8, and run it at http://ideone.com/3zRNil. I’m sure I got some things wrong about Clojure, and would appreciate corrections from readers who are proficient with Clojure.
Programming Praxis 
Project Euler problem 3 in Erlang using a 2,3,5,7 factor wheel. The main routine is pretty much like how to factor a number in any functional programming language.
wheel2357() -> Start = [1, 2, 2, 4], Wheel = [ 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10], cycle:new(Start, Wheel). factorize(N) -> lists:reverse(factorize(abs(N), wheel2357(), 2, [])). factorize(N, Wheel, Fac, Factors) -> if Fac*Fac > N -> [N | Factors]; N rem Fac =:= 0 -> factorize(N div Fac, Wheel, Fac, [Fac | Factors]); true -> factorize(N, Wheel, Fac + cycle:next(Wheel), Factors) end. main(_) -> test_wheel(), io:format("The factors of 600,051,475,143 are ~p~n", [factorize(600851475143)]).Erlang does not have a facility to create a cirular list, so to create the wheel I create a new process (actually a very lightweight thread) to simulate a generator that can yield a new value each time it is called.
-module(cycle). -export([new/2, next/1, loop/2]). -spec new([any()], [any()]) -> pid(). new(Pfx, Seq) -> spawn_link(?MODULE, loop, [Pfx, Seq]). -spec next(pid()) -> any(). next(ProcID) -> ProcID ! {self(), next}, receive {ProcID, Response} -> Response end. loop(Prefix, Cycle) -> receive {From, next} -> case Prefix of [First | Rest] -> From ! {self(), First}, loop(Rest, Cycle); [] -> [First | Rest] = Cycle, From ! {self(), First}, loop(Rest, Cycle) end; {From, _} -> From ! {self(), message_not_understood}, loop(Prefix, Cycle) end.