Converting to TCO

[Robert Campbell]

I've started reading SICP and I came across the Fermat primality test
implemented an Scheme. I reimplemented it in Clojure and was able to
switch the recursive call in fast-prime to TCO/recur, but I was unable
to do the same for the exp-mod function.

(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)))

(defn fermat-test [n]
(defn try-it [a]
(= (exp-mod a n n) a))
(try-it (inc (rand-int (dec n)))))

(defn fast-prime? [n times]
(cond
(zero? times) true
(fermat-test n) (recur n (dec times))
:else false))

Calling (fast-prime? 5 3) blows the stack. How can I change exp-mod to use TCO?

[Robert Campbell]

One correction: after playing with the functions a bit I noticed I
screwed up, putting sqrt where I needed square.

[Mark Engelberg]

Hint: Use an accumulator.
http://htdp.org/2003-09-26/Book/curriculum-Z-H-39.html#node_chap_31

In fact, you may want to consider reading How to Design Programs before SICP.

[John Harrop]

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))))))

[Robert Campbell]

Mark: that looks a lot like the "collector" I learned about in The
Little Schemer. I actually do have How to Design Programs, but I
wanted to finish Seasoned Schemer first. I was poking around in SICP
because of a Project Euler problem. Thanks for the tip!

John: good catch. Can you confirm the difference between my original
defn and your letfn? Both work, but as I understand it from the
documentation, defn would actually define that local function
globally, while letfn actually does bind it locally to all the expr
which follow in the body..

[John Harrop]

On Sun, Nov 8, 2009 at 1:39 PM, Robert Campbell <rrc...@gmail.com> wrote:

John: good catch.

Thanks.

 

Can you confirm the difference between my original
defn and your letfn? Both work, but as I understand it from the
documentation, defn would actually define that local function
globally, while letfn actually does bind it locally to all the expr
which follow in the body..

Yup.