You have a bug: (defn exp-mod [base exp m] (cond (zero? exp) 1 (even? exp) (mod (Math/sqrt (exp-mod base (/ exp 2) m)) m) :else (mod (* base (exp-mod base (inc exp) m)) m)))
should be (defn exp-mod [base exp m] (cond (zero? exp) 1 (even? exp) (mod (Math/sqrt (exp-mod base (/ exp 2) m)) m) :else (mod (* base (exp-mod base (dec exp) m)) m))) The recursion depth is logarithmic in exp so TCO is probably unnecessary here. But with the bug, it gets locked into a cycle of exp being alternately 2 and 1 and never reaching zero, the base case, so the recursion continues until the stack blows up. Meanwhile, (defn fermat-test [n] (defn try-it [a] (= (exp-mod a n n) a)) (try-it (inc (rand-int (dec n))))) should really be (defn fermat-test [n] (letfn [(try-it [a] (= (exp-mod a n n) a))] (try-it (inc (rand-int (dec n)))))) in Clojure, or even (defn fermat-test "Performs the Fermat test on n with a, if specified, or with a random value from 2 to n." ([n a] (= (exp-mod a n n) a)) ([n] (fermat-test n (inc (rand-int (dec n)))))) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---