1.16
(define (fast-expt x n)
(fast-expt-iter x n 1))
(define (fast-expt-iter x n a)
(cond ((= n 0) a)
((even? n) (fast-expt-iter (square x)
(/ n 2)
a))
(else (fast-expt-iter x
(- n 1)
(* a x)))))
1.17
(define (multi x y)
(if (= y 0)
0
(+ x (multi x (- y 1)))))
(define (fast-multi x y)
(cond ((= y 0) 0)
((even? y) (double (fast-multi x
(half y))))
(else (+ x (fast-multi x (- y 1))))))
(define (double x) (+ x x))
(define (half y) (/ y 2))
1.18
(define (double x) (+ x x))
(define (half y) (/ y 2))
(define (fast-multi x y)
(fast-multi-iter x y 0))
(define (fast-multi-iter x y p)
(cond ((= y 0) p)
((even? y) (fast-multi-iter (double x)
(half y)
p))
(else (fast-multi-iter x (- y 1) (+ p x)))))
1.19
;T(pq):(a,b)=>(bq+aq+ap, bp+aq)
;T(pq):(bq+aq+ap, bp+aq)=>((bp+aq)q + (bq+aq+ap)q + (bq+aq+ap)p,
; (bp+aq)p + (bq+aq+ap)q)
; => (2bpq+2aqq+bqq+2apq+app, bpp+2apq+bqq+aqq)
; => (b(2pq+qq)+a(2pq+qq)+a(qq+pp), b(qq+pp)+a(2pq+qq))
;q' = 2pq+qq
;p' = qq+pp
;
(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))
(+ (* 2 p q ) (* q q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))