SICP Exercises 1.16 - 1.19

This post contains my solutions to exercises from Section 1.2.4 “Exponentiation” of the book “Structure and Interpretation of Computer Programs” that I’m working through as part of my “Learning Computer Science” project. You can find an online version of the text at the companion website for the book.

Exercise 1.16

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

Exercise 1.17

(define (double n)
  (+ n n))
(define (halve n)
  (/ n 2))
(define (fast-multiply a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (halve b))))
        (else (+ a (fast-multiply a (- b 1))))))

Exercise 1.18

The invariant quantity I picked in this case is a+b*c. As defined in the hint of exercise 1.16, an invariant quantity remains constant throughout the iterative process. For the following procedure, this means that when the three arguments of iter are used to compute a+b*c, they will give the same value at any state of the generated iterative process (e.g. (iter 0 5 6), (iter 0 10 3), and (10 20 1), etc.).

(define (fast-multiply b c)
  (define (double n)
    (+ n n))
  (define (halve n)
    (/ n 2))
  (define (iter a b c)
    (cond ((= c 0) a)
          ((even? c) (iter a (double b) (halve c)))
          (else (iter (+ a b) (double b) (halve (- c 1))))))
  (iter 0 b c))

Exercise 1.19

\[T_{pq}=(bq+aq+ap,bp+aq)\\ T_{pq}^2=T_{pq}(bq+aq+ap,bp+aq)\\ \quad= ((bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)p, (bp+aq)p+(bq+aq+ap)q)\\ \quad= (b(q^2+2pq)+a(q^2+2pq)+a(p^2+q^2), b(p^2+q^2)+a(q^2+2pq))\\ \quad= T_{p'q'}(a,b);\text{ where, } p'=p^2+q^2 \text{ and } q'=q^2+2pq\]

Thus, the completed procedure is:

(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
                   (+ (* p p) (* q q))
                   (+ (* q q) (* 2 p q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))



Recent Posts

Aug​ 3, 2022 Peeling Back The Onion
Apr​ 13, 2022 Test Your APIs For Spring4Shell With Levo.ai
Mar​ 8, 2022 ZAPCon 2022 Presentation Resources
Dec​ 14, 2021 Log4Shell Detection with ZAP
Aug​ 30, 2021 Soaring Through the Stars as an Astra-Naut
Aug​ 23, 2021 Out-of-band Application Security Testing with OWASP ZAP
Jul​ 11, 2021 ZAP OAST: Basic Design Decisions
Jun​ 25, 2021 Levelling Up ZAP with OAST
Jan​ 5, 2021 SICP Exercises 1.11 - 1.15
Nov​ 30, 2020 Hot-swappable Jekyll Themes
See the Archive for a full list.