exercise-19.scm (1718B)
1 (define-library (sicp solutions chapter-1 exercise-19) 2 (import (scheme base)) 3 (export fib 4 fast-fib) 5 6 ;;; T 7 ;;; a <- (a + b) 8 ;;; b <- a 9 ;;; 10 ;;; Tpq = 11 ;;; a <- bq + aq + ap 12 ;;; a <- bq + a(q + p) 13 ;;; b <- bp + aq 14 ;;; 15 ;;; Tpq^2 = 16 ;;; a' <- (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p 17 ;;; a' <- bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2 18 ;;; a' <- 2bpq + 2aq^2 + bq^2 + 2apq + ap^2 19 ;;; a' <- b(2pq + q^2) + (2apq + ap^2 + 2aq^2) 20 ;;; a' <- b(2pq + q^2) + a(2pq + p^2 + 2q^2) 21 ;;; q = 2pq + q^2 22 ;;; p + q = 2pq + p^2 + 2q^2 23 ;;; p = (2pq + p^2 + 2q^2) - (2pq + q^2) 24 ;;; p = 2pq + p^2 + 2q^2 - 2pq - q^2 25 ;;; p = p^2 + q^2 26 ;;; a' <- b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2) 27 ;;; 28 ;;; oh. i'm dumb. we already have q' and p' in terms of q and p here: 29 ;;; 30 ;;; b' <- (bp + aq)p + (bq + aq + ap)q 31 ;;; b' <- bp^2 + apq + bq^2 + aq^2 + apq 32 ;;; b' <- bp^2 + 2apq + bq^2 + aq^2 33 ;;; b' <- bp^2 + bq^2 + 2apq + aq^2 34 ;;; b' <- b(p^2 + q^2) + a(2pq + q^2) 35 36 (begin 37 (define (fib n) 38 (cond 39 ((= n 0) 0) 40 ((= n 1) 1) 41 (else (+ (fib (- n 1)) 42 (fib (- n 2)))))) 43 44 (define (fast-fib n) 45 (define (fib-iter a b p q count) 46 (cond 47 ((= count 0) b) 48 ((even? count) 49 (fib-iter a 50 b 51 (+ (* p p) 52 (* q q)) 53 (+ (* 2 p q) 54 (* q q)) 55 (/ count 2))) 56 (else 57 (fib-iter (+ (* b q) 58 (* a q) 59 (* a p)) 60 (+ (* b p) 61 (* a q)) 62 p 63 q 64 (- count 1))))) 65 (fib-iter 1 0 0 1 n))))