Books by Example/SICP2007.11.17 17:50

본문에 나오는 이야기입니다만, T(a,b): (a <- a + b, b <- a)라고 하고, T 규칙을 순차적으로 n번 적용한 것을 T^n이라고 하면, T^n(1,0)은 n번째 피보나치 수열이죠.

그런데 사실 이 규칙 T는

  T_{p,q}(a,b): (a <- bq + aq + ap, b <- bp + aq)

의 특별한 케이스(p=0, q=1)입니다.

여기까지를 알고 있을때, 규칙 T_{p,q}를 연속적으로 두 번 적용해 보면(T_{p,q}^2) 어떻게 되나요?

a <- (bp + aq)q + (bq+aq+ap)q + (bq+aq+ap)p
       = b(2pq+q^2) + a(2pq+q^2) + a(p^2+q^2)
b <- (bp+aq)p + (bq+aq+ap)q
       = b(p^2 + q^2) + a(2pq+q^2)

결국, p^2+q^2 = p', 2pq+q^2 = q'로 놓게되면

  a <- bq' + aq' + ap', b <- bp' + aq'

이 됩니다.

그렇다면 피보나치 수열을 계산하는데 필요한 인자를 a, b, p, q의 네 가지로 보았을 때, 이터레이션의 수를 반으로 줄이고 싶으면 그럴 때 마다 a, b, p, q를 a, b, p^2+q^2, 2pq+q^2로 바꾸면 되겠군요. 그렇게 할 수 없을 때에는 a, b, p, q를 bq+aq+ap, bp+aq, p, q로 바꾸면 되고요.

맨 마지막에는 이렇게 해서 만들어진 최종 4-tuple을 다시 (a, b, p, q)라고 했을 때 b를 반환하도록 하면 되겠습니다.

그렇다면 결국 책에 나온 Scheme 문제는 다음과 같이 채우면 되겠군요.

(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)))))

이 문제는 Scheme 식으로 생각하는 문제라기 보다는 수학 문제처럼 느껴진다는...


신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. 전 피보나치 수열을 로그 차수가 나오는 알고리즘이 있다는 점이 무척 신기했습니다.^^

    2008.01.14 11:31 신고 [ ADDR : EDIT/ DEL : REPLY ]