adrianwong programmer · retired coal miner

SICP section 1.2 - procedures and the processes they generate

Selected exercises

Exercise 1.09

First definition is recursive:

(define (+ a b)
  (if (= a 0) b (inc (+ (dec a) b))))

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

Second definition is iterative:

(define (+ a b)
  (if (= a 0) b (+ (dec a) (inc b))))

(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9

Exercise 1.11

Implementing \(f\) as a recursive process is fairly trivial:

(define (fr n)
  (if (< n 3)
      n
      (+ (fr (- n 1))
         (+ (* 2 (fr (- n 2)))
            (* 3 (fr (- n 3)))))))

Implementing \(f\) as an iterative process is slightly trickier, but very similar to the iterative Fibonacci process covered in section 1.2.2. The idea is to use three integers \(a\), \(b\) and \(c\), initialised to \(f(2) = 2\), \(f(1) = 1\) and \(f(0) = 0\), and to repeatedly apply the simultaneous transformations:

$$\begin{align*} a &\leftarrow a + 2b + 3c \\ b &\leftarrow a \\ c &\leftarrow b \\ \end{align*}$$

On \(n\) applications, \(a\), \(b\) and \(c\) are equal to \(f(n + 2)\), \(f(n + 1)\) and \(f(n)\) respectively.

(define (fi n)
  (fi-iter 2 1 0 n))

(define (fi-iter a b c n)
  (if (= n 0)
      c
      (fi-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- n 1))))

Testing that both processes output the same values:

(define (test n)
  (if (= n 0)
      (= (fr 0) (fi 0))
      (and (= (fr n) (fi n)) (test (- n 1)))))

Exercise 1.12

Note: this solution uses 1-based numbering for rows and columns. Key points:

$$val(r, c) = val(r - 1, c - 1) + val(r - 1, c)$$
(define (pascal row col)
  (cond ((or (< col 1) (> col row)) 0) ; Error conditions
        ((or (= col 1) (= col row)) 1) ; Base cases
        (else (+ (pascal (- row 1) (- col 1))
                 (pascal (- row 1) col)))))

Exercise 1.16

(define (square n) (* n n))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))

(define (fast-expt b n)
  (fast-expt-iter b n 1))

To gain a better intuition for the fast-expt-iter process, we can step through a computation of \(2^8\):

(fast-expt-iter 2 8 1)
(fast-expt-iter 4 4 1)
(fast-expt-iter 16 2 1)
(fast-expt-iter 256 1 1)
(fast-expt-iter 256 0 (* 1 256))
(fast-expt-iter 256 0 256)
256

Exercise 1.19

From applying the transformation \(T_{pq}\) once, we have the equations:

$$\begin{align} a_1 &= bq + a(q + p) \\ b_1 &= bp + aq \\ \end{align}$$

From applying the transformation \(T_{pq}\) a second time, we have the equations:

$$\begin{align} a_2 &= b_1q + a_1(q + p) \\ b_2 &= b_1p + a_1q \\ \end{align}$$

We want to represent \(p_1\) and \(q_1\) in terms of \(p\) and \(q\). Substituting \((1)\) and \((2)\) into \((4)\), and manipulating the equation to fit the form \(b_2 = bp_1 + aq_1\):

$$\begin{align*} b_2 &= (bp + aq)p + (bq + aq + ap)q \\ &= b(p^2) + b(q^2) + 2apq + a(q^2) \\ &= b(p^2 + q^2) + a(2pq + q^2) \\ p_1 &= (p^2 + q^2) \\ q_1 &= (2pq + q^2) \end{align*}$$

Verify by substituting \((1)\) and \((2)\) into \((3)\), and manipulating the equation to fit the form \(a_2 = bq_1 + a(q_1 + p_1)\):

$$\begin{align*} a_2 &= (bp + aq)q + (bq + aq + ap)(q + p) \\ &= 2bpq + b(q^2) + 2apq + 2a(q^2) + a(p^2) \\ &= b(2pq + q^2) + a((2pq + q^2) + (p^2 + q^2)) \\ p_1 &= (p^2 + q^2) \\ q_1 &= (2pq + q^2) \end{align*}$$

Using the values of \(p_1\) and \(q_1\) in the fib-iter procedure:

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

Exercise 1.25

Stepping through Alyssa’s version using test values \(base = 5\) and \(exp = 8\). These values are small, but are sufficient to illustrate the issue with Alyssa’s approach:

; For brevity, `remainder` -> `rmd`
(expmod 5 8 8)
(rmd (fast-expt 5 8) 8)
(rmd (square (fast-expt 5 4)) 8)
(rmd (square (square (fast-expt 5 2))) 8)
(rmd (square (square (square (fast-expt 5 1)))) 8)
(rmd (square (square (square (* 5 (fast-expt 5 0))))) 8)
(rmd (square (square (square (* 5 1)))) 8)
(rmd (square (square (square 5))) 8)
(rmd (square (square 25)) 8)
(rmd (square 625) 8)
(rmd 390625 8)
1

Stepping through the authors’ version with the same parameters:

; For brevity, `remainder` -> `rmd`
(expmod 5 8 8)
(rmd (square (expmod 5 4 8)) 8)
(rmd (square (rmd (square (expmod 5 2 8)) 8)) 8)
(rmd (square (rmd (square (rmd (square (expmod 5 1 8)) 8)) 8)) 8)
...
(rmd (square (rmd (square (rmd (square (rmd 5 8)) 8)) 8)) 8)
(rmd (square (rmd (square (rmd (square 5) 8)) 8)) 8)
(rmd (square (rmd (square (rmd 25 8)) 8)) 8)
(rmd (square (rmd (square 1) 8)) 8)
(rmd (square (rmd 1 8)) 8)
(rmd (square 1) 8)
(rmd 1 8)
1

Alyssa’s version first computes the exponential value, then computes the remainder - this generates huge intermediary numbers, which are computationally expensive. The results generated are still correct, but the execution time is much slower.

The authors’ version keeps the numbers being squared less than the number being tested for primality, as it applies remainder to the result of every application of square.

Exercise 1.26

The explicit multiplication that Louis uses requires a double call to expmod. This transforms a linear recursive process into a tree recursive process, which causes the number of recursive calls to grow exponentially.

New time complexity:

$$\begin{align*} T(n) &= O(log_2 (2^n)) \\ &= O(n (log_2 2)) \\ &= O(n) \end{align*}$$