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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
