SICP Exercise 1.19

연습문제 1.19: 피보나치 수열을 구하는 계산 단계가 다음과 같이 로그
차수로 자라나는 코드로 작성할 수 있다. 여기서 p = 0, q = 1이면
피보나치 수열을 구하는 함수가 된다. 여기서, (T_pq)^2 = T_p'q' 임을
증명하고, p와 q로 p'와 q'를 계산하는 식을 구하라. 이는 아래 코드의
update-pupdate-q 함수의 내용이 될 것이다.

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

T_p'q' = (T_pq)^2는 다음과 같이 정리할 수 있다.

a <- bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
  <- 2(a+b)pq + (2a+b)q^2 + ap^2
   = bq' + aq' + ap'

b <- bp^2 + apq + bq^2 + aq^2 + apq
  <- 2apq + (a+b)q^2 + bp^2
   = bp' + aq'

윗 식을 정리하면, p'q'은 다음과 같이 구할 수 있다.

p' = p^2 + q^2
q' = 2pq + q^2

이를 update-pupdate-q 함수로 표현하고 전체 코드를 clojure로
다시 작성한 답은 다음과 같다.

(defn update-p [p q]
  (+ (* p p) (* q q)))

(defn update-q [p q]
  (+ (* 2 p q) (* q q)))

(defn fib-iter [a b p q count]
  (cond
   (= count 0) b
   (even? count) (fib-iter a
                           b
                           (update-p p q)
                           (update-q p q)
                           (/ count 2))
   :else (fib-iter (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (dec count))))

(defn fib [n]
  (fib-iter 1 0 0 1 n))