태터데스크 관리자

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

태터데스크 메시지

저장하였습니다.

'fibonacci'에 해당되는 글 2건

  1. 2007.11.05 Fibo2 ... (3)
  2. 2007.11.02 Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1 (4)

Fibo2 ...

Tech 2007. 11. 5. 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 : fibonacci, scheme, SICP
Trackbacks 0 : Comments 3
  1. Favicon of https://deisys.tistory.com 가난한 d-goon 2007.11.05 23:19 신고 Modify/Delete Reply

    Interesting - Lame's Theorm - If Euclid's Algorithm requires k steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the kth Fibonacci number.

  2. Favicon of http://etnalry.tistory.com etnalry 2007.11.06 14:13 신고 Modify/Delete Reply

    이번엔 스킴인가?
    피보나치 때문에 점점 도인의 세계로 들어가고 있는 것 같군. ㅋ

Write a comment


Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1

Tech 2007. 11. 2. 23:26
재귀호출이나 반복문의 예제로 자주 나오는 피보나치 수열. 이렇게 구할 수도 있다. 음, recursion tree의 terminal node를 세면(그럴싸한 방법이지?) fib(n) = pi^n / sqrt(5) 에 가장 근접한 정수, pi = (1+sqrt(5))/2  와 같은 식을 얻을 수 있다(고 한다). 이걸 보니 정말? 이라는 생각이 들어 C로 만들어 봤다... sqrt 함수를 직접 만들어 썼더니 fib(63) 에서 1의 오차가 생겼고, sqrt 를 math.h 에서 가져다 썼더니 fib(72) 에서 1의 오차가 생기기 시작... 대략 잘 맞는다. 신기하구먼 ㅎㅎㅎ

#include <stdio.h>
#include <math.h>

typedef long long ll;

ll fibo(int n) {
        double pi = 0.5*(1.0 + sqrt(5));
        double t = 1.0;
        int i;

        for (i = 0; i < n; i++)
                t *= pi;

        return (ll)((t + 0.5)/sqrt(5));
}

int main(int argc, char ** argv) {
        int n = atoi(argv[1]);

        printf("%llu\n", fibo(n));

        return 0;
}

이나이 되도록 이런것도 모르고... 공부좀 더 해야겠다. ㅠ_ㅠ

'Tech' 카테고리의 다른 글

하둡의 퍼포먼스 (삽질기)  (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
SSH Key distribution  (2) 2007.10.24
tags : fibonacci, SICP
Trackbacks 0 : Comments 4
  1. Favicon of http://etnalry.tistory.com etnalry 2007.11.04 17:27 신고 Modify/Delete Reply

    return (ll) ((t + 0.5) / sqrt(5)); ==> return (ll) (t / sqrt(5) + 0.5);
    이렇게 해보면?

  2. Favicon of http://deisys.net deisys 2007.11.04 20:57 Modify/Delete Reply

    얼라? 그러게... 왜 저게 안에 있었지? (;;; 나 바보 ?)

    근데 그렇게 바꿔도 72에서 오차 생기기 시작하는건 같군. ㅎㅎ

  3. Favicon of http://waityet.tistory.com waityet 2008.03.07 22:52 Modify/Delete Reply

    심심해서 둘러보다가.
    피보나치라..중3때인가. 난데없이 선형대수책을 들고와서 일반항을 구하는 짓을
    누군가가 해줬던거 같은데.. 대체 왜 그랬는지는 기억이 없지만.
    수학적으로 equivalent한 것들에 대한 새로운 경험이었던 것으로 기억됨.

Write a comment