Jesse's Blog

Exercise 1.16

'In general, the technique to defining an invariant quantity that remains
unchanged from state to state is a powerful way to think about the design of
iterative algorithms.'

1 * b^n
=> 1 * (b^2)^(n/2) (n is even)
=> b * b^(n-1) (n is odd)

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

Exercise 1.17

(define (double a)
 (+ a a))
(define (halve a)
 (/ a 2))

(define (mul a b)
  (cond ((= b 0) 0)
        ((even? b) (mul (double a) (halve b)))
        (else (+ a (mul a (- b 1)))))

Exercise 1.18

a*b
0 + a*b
=> 0 + (2a)*(b/2)
=> b + a*(b-1)

(define (double a)
  (+ a a))

(define (halve a)
  (/ a 2))

(define (mul a b)
  (define (mul-iter m a b)
   (cond ((= b 0) m)
         ((even? b) (mul-iter m (double a) (halve b)))
         (else (mul-iter (+ m a) a (- b 1)))))
  (mul-iter 0 a b)

Exercise 1.19

b is the small one and a is big.

(define (T a b p q n)
 (define (update-p)
   (+ (square p) (square q)))
 (define (update-q)
   (+ (* 2 p q) (square q)))
 (define (trans-a)
   (+ (* b q) (* a q) (* a p)))
 (define (trans-b)
   (+ (* b p) (* a q)))

  (cond ((= n 0) b)
        ((even? n) (T a b (update-p) (update-q) (/ n 2)))
        (else (T (trans-a) (trans-b) p q (- n 1)))))


(define (fib n)
  (T 1 0 0 1 n)