SICP Exercise 1.21: Smallest Divisor

Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

This exercise is simply a case of invoking the procedure smallest-divisor in an interpreter with the given values. I get the following results:

> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7

SICP Exercise 1.20: Interpreting GCD

The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section 1.1.5. (The normal-order-evaluation rule for if is described in exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?

Let's play at being an interpreter again... Just to recap, the definition of gcd is:

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

Using normal order evaluation we don't evaluate any of the operands until their values are required. Instead, as it says in section 1.1.5, we "fully expand and then reduce", so here's a full (and somewhat long) expansion and reduction of (gcd 206 40). I've highlighted each occurrence of remainder that gets evaluated on the next line:

  (gcd 206 40)
= (if (= 40 0)
      206
      (gcd 40
           (remainder 206 40)))
= (if #f
      206
      (gcd 40
           (remainder 206 40)))
= (gcd 40
       (remainder 206 40))
= (if (= (remainder 206 40) 0)
      40
      (gcd (remainder 206 40)
           (remainder 40
                      (remainder 206 40))))
= (if (= 6 0)
      40
      (gcd (remainder 206 40)
           (remainder 40
                      (remainder 206 40))))
= (if #f
      40
      (gcd (remainder 206 40)
           (remainder 40
                      (remainder 206 40))))
= (gcd (remainder 206 40)
       (remainder 40
                  (remainder 206 40)))
= (if (= (remainder 40
                    (remainder 206 40))
         0)
      (remainder 206 40)
      (gcd (remainder 40
                      (remainder 206 40))
           (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))))
= (if (= (remainder 40 6) 0)
      (remainder 206 40)
      (gcd (remainder 40
                      (remainder 206 40))
           (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))))
= (if (= 4 0)
      (remainder 206 40)
      (gcd (remainder 40
                      (remainder 206 40))
           (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))))
= (if #f
      (remainder 206 40)
      (gcd (remainder 40
                      (remainder 206 40))
           (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))))
= (gcd (remainder 40
                  (remainder 206 40))
       (remainder (remainder 206 40)
                  (remainder 40
                             (remainder 206 40)))))
= (if (= (remainder (remainder 206 40)
                    (remainder 40
                               (remainder 206 40)))
         0)
      (remainder 40
                 (remainder 206 40))
      (gcd (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))
           (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))))
= (if (= (remainder 6
                    (remainder 40
                               (remainder 206 40)))
         0)
      (remainder 40
                 (remainder 206 40))
      (gcd (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))
           (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))))
= (if (= (remainder 6
                    (remainder 40 6))
         0)
      (remainder 40
                 (remainder 206 40))
      (gcd (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))
           (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))))
= (if (= (remainder 6 4) 0)
      (remainder 40
                 (remainder 206 40))
      (gcd (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))
           (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))))
= (if (= 2 0)
      (remainder 40
                 (remainder 206 40))
      (gcd (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))
           (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))))
= (if #f
      (remainder 40
                 (remainder 206 40))
      (gcd (remainder (remainder 206 40)
                      (remainder 40
                                 (remainder 206 40)))
           (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))))
= (gcd (remainder (remainder 206 40)
                  (remainder 40
                             (remainder 206 40)))
       (remainder (remainder 40
                             (remainder 206 40))
                  (remainder (remainder 206 40)
                             (remainder 40
                                        (remainder 206 40))))))
= (if (= (remainder (remainder 40
                               (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40))))
         0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= (remainder (remainder 40 6)
                    (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40))))
         0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= (remainder 4
                    (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40))))
         0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= (remainder 4
                    (remainder 6
                               (remainder 40
                                          (remainder 206 40))))
         0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= (remainder 4
                    (remainder 6
                               (remainder 40 6)))
         0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= (remainder 4
                    (remainder 6 4))
         0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= (remainder 4 2) 0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if (= 0 0)
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (if #t
      (remainder (remainder 206 40)
                 (remainder 40
                            (remainder 206 40)))
      (gcd (remainder (remainder 40
                                 (remainder 206 40))
                      (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40))))
           (remainder (remainder (remainder 206 40)
                                 (remainder 40
                                            (remainder 206 40)))
                      (remainder (remainder 40
                                            (remainder 206 40))
                                 (remainder (remainder 206 40)
                                            (remainder 40
                                                       (remainder 206 40)))))))
= (remainder (remainder 206 40)
             (remainder 40
                        (remainder 206 40)))
= (remainder 6
             (remainder 40
                        (remainder 206 40)))
= (remainder 6
             (remainder 40 6))
= (remainder 6 4)
= 2

Phew! Counting up all the highlighted occurrences of remainder tells us that this required a total of 18 applications of remainder.

Thankfully, using applicative-order evaluation is much simpler, as we evaluate each of the operands to an operator before we apply the operator. So, once again, here's the evaluation of (gcd 206 40), but this time using applicative-order evaluation:

   (gcd 206 40)
= (if (= 40 0) 206 (gcd 40 (remainder 206 40)))
= (if #f 206 (gcd 40 (remainder 206 40)))
= (gcd 40 (remainder 206 40))
= (gcd 40 6)
= (if (= 6 0) 40 (gcd 6 (remainder 40 6)))
= (if #f 40 (gcd 6 (remainder 40 6)))
= (gcd 6 (remainder 40 6))
= (gcd 6 4)
= (if (= 4 0) 6 (gcd 4 (remainder 6 4)))
= (if #f 6 (gcd 4 (remainder 6 4)))
= (gcd 4 (remainder 6 4))
= (gcd 4 2)
= (if (= 2 0) 4 (gcd 2 (remainder 4 2)))
= (if #f 4 (gcd 2 (remainder 4 2)))
= (gcd 2 (remainder 4 2))
= (gcd 2 0)
= (if (= 0 0) 2 (gcd 0 (remainder 2 0)))
= (if #t 2 (gcd 0 (remainder 2 0)))
= 2

Without even counting we can see from the brevity of the evaluation (both in terms of number of lines and length of lines) that the applicative-order evaluation requires much less state to be maintained, and fewer steps. There are a total of 4 applications of remainder required here.

Of course it's worth noting that a system that did implement normal-order evaluation may well cache the results of evaluations (or even evaluate a procedure once and then substitute its result in all places where it can be used), so in actuality the difference between the two may be less pronounced as this.

SICP Exercise 1.19: Fibonacci on Steroids

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2: a ← a + b and b ← a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying T_n, the n^th power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations T_pq, where T_pq transforms the pair (a,b) according to a ← bq + aq + ap and b ← bp + aq. Show that if we apply such a transformation T_pq twice, the effect is the same as using a single transformation T_p'q' of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute T_n using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                         ; compute p'
                         ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

We're given the transformation:

Tpq(a, b) = ((bq + aq + ap), (bp + aq))

If we apply the transformation T_pq to itself then we get the following:

  Tpq(Tpq(a, b))
= Tpq((bq + aq + ap), (bp + aq))
= (((bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p), ((bp + aq)p + (bq + aq + ap)q))
= ((bpq + aq2  + bq2 + aq2 + apq + bpq + apq + ap2), (bp2 + apq + bq2 + aq2 + apq))
= ((b(q2 + 2pq) + a(q2 + 2pq) + a(p2 + q2)), (b(p2 + q2) + a(q2 + 2pq)))

Now if we define p' and q' as:

p' = p2 + q2
q' = q2 + 2pq

...then this gives:

Tpq(Tpq(a, b)) = ((bq' + aq' + ap'), (bp' + aq'))

...which is of the same form as the transform T_pq, and so we can define T_p'q'(a, b) as:

  Tp'q'(a, b)
= ((bq' + aq' + ap'), (bp' + aq'))
= ((b(q2 + 2pq) + a(q2 + 2pq) + a(p2 + q2)), (b(p2 + q2) + a(q2 + 2pq)))

We can now simply plug the mappings for p' and q' into the template procedure above to give:

(define (fib n) (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (* 2 p q) (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Finally, we can check it works as expected:

> (fib 0)
0
> (fib 1)
1
> (fib 2)
1
> (fib 3)
2
> (fib 4)
3
> (fib 5)
5
> (fib 6)
8
> (fib 7)
13
> (fib 8)
21