태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

Fibo2 ...

Tech 2007.11.05 23:02
SICP Exercise 1.19

a <- bq + aq + ap
b <- bp + aq
Transformation T, 그리고 p=0, q=1 에서 시작, 이것이 피보나치 수열을 구하는 transformation 이라고?

당연히 T^n 은 n번째 피보나치 수열을 구하는 Transformation 이 된다. 이것은 successive squaring에 사용할 수 있다. 이를 이용하여 피보나치 수열을 구하는 함수를 만들면,

(define (fibo2 n)
 (define (square x)
  (* x x))
 (define (fib-iter a b p q counter)
  (cond ((= counter 0) b)
        ((even? counter) (fib-iter a
                                   b
                                   (+ (square p) (square q))
                                   (+ (square q) (* 2 (* p q)))
                                   (/ counter 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- counter 1)))))
 (fib-iter 1 0 0 1 n))

기본 Iteration 으로 5만번째 피보나치 수를 구하는데 15초, 위 코드로 50만번째 피보나치 수를 구하는데 5초...

사실 transformation 은 2x2 행렬이므로 p, q, r, s 네개의 변수가 있으면 가능하다. 하지만 r, s 도 p, q를 이용하여 표현할 수 있나보다. 피보나치 행렬(?)은 두개의 변수로 표현 가능하다고 하는데... 연습장을 조금 더 끄적여봐야 겠음.

전에꺼도 제곱으로 하는거라 successive squaring은 되는데... 숫자가 너무 커지면 낭패니 C로는 무리. 그렇다고 스킴이나 루비같은걸로 옮기기도 귀찮. ;;

'Tech' 카테고리의 다른 글

ofstream redirect to stdout  (3) 2007.11.10
하둡의 퍼포먼스 (삽질기)  (7) 2007.11.09
Fibo2 ...  (3) 2007.11.05
Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1  (4) 2007.11.02
Nutch Crawler, briefly  (1) 2007.10.31
String matching  (3) 2007.10.31
tags : , ,
Trackbacks 0 : Comments 3