최근 수정 시각 : 2024-10-09 04:35:32

피보나치 수열

이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"
이론
<colbgcolor=#3CC> 기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


1. 개요2. 유래3. 일반항의 유도4. 성질5. 음의 피보나치 수열6. 유리수에서7. 활용8. 알고리즘
8.1. 분할 정복을 이용한 알고리즘 [math(\mathcal{O}(\log n) )]
9. 여담10. 관련 문서

1. 개요

Fibonacci sequence. 수학에서 다루는 수열이다. 다음과 같은 점화식으로 피보나치 수열을 정의할 수 있다.
[math(F_0=0, \ F_1=1, \ F_{n+2}=F_{n+1}+F_{n})]
일반항으로 표현하자면 다음과 같다.
[math(\begin{aligned}
F_n &= \dfrac 1 {\sqrt 5} \left[ \left(\dfrac{1 + \sqrt 5} 2\right)^n - \left(\dfrac{1 - \sqrt 5} 2\right)^n \right] \\
&= \dfrac{\left(1 + \sqrt 5\right)^n - \left(1 - \sqrt 5\right)^n}{2^n \sqrt 5} \\
&= \dfrac 1 {2^{n - 1}} \sum^{\lfloor(n+1)/2\rfloor}_{k = 0} \dbinom n {2k + 1} 5^k
\end{aligned})]
([math(\lfloor (n+1)/2 \rfloor)]는 [math((n+1)/2)]이하의 최대정수, [math(\binom{n}{2k-1})]은 조합)
아주 계산이 복잡하다. 다항방정식 형태로 바꿔서 풀면 쉽다.

제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다. 이 둘은 시작점이 다르다는 정도를 빼면 사실상 동일하다.

그 중에서 16 번째 항까지만 나열해 보자면 (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
이렇게 간다.

피보나치 수열의 이웃한 두 항이 항상 서로소라는 것은 수학적 귀납법으로 쉽게 증명할 수 있다. 피보나치 소수[1]가 무한히 존재하는지는 유명한 미해결 문제다.[2]

2. 유래

피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방 쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 가설들도 있긴 하나 공식적인 연관성은 아직 불분명하다. 물론 피보나치가 중세 중동 지역의 수학 서적들을 대거 번역하여 유럽 문명에 소개했던 주인공이었으므로,[3] 인도와 중동에서 발전한 체계적이고 심도있는 수학적 지식을 깊이 공부하던 도중에 피보나치 수열의 아이디어를 차용했을 가능성은 충분히 있다. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에, 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치수열이란 이름은 19세기가 되어서야 붙여졌다.

실제 피보나치 수열의 점화식은 인도도 그렇고 유럽도 그렇고 일찌감치 알려져 있었으나 피보나치 수의 생성함수는 완전히 정리되기까지 다소 시간이 필요했다. 1765년 오일러가 최초로 이 생성함수를 정리하여 발표했으나 당시에는 별로 주목을 받지 못해서 그대로 묻혔다. 이후 1848년 비네가 이 생성함수를 재발견하여 발표했고 결국 피보나치 수의 생성함수는 비네의 식이라 이름이 붙었다. 물론 오일러는 다른 방면에서도 어마어마하게 유명하므로 아쉬울 일은 없을 것이다.

수학의 수열 파트에서 잠시 배우는 수준이지만 컴퓨터 계열로 진학할 경우 정말 질리도록 보게 된다. 프로그래밍 언어에서 재귀함수를 배우면서 과제로 반드시 한 번은 하게 된다. 재귀함수로 간단히 구현되지만, 메모이제이션(Memoization) 없이 구현할 경우 실행시간이 안드로메다로 증가하게 된다. 반대로 메모이제이션을 할 경우에는 필요한 메모리가 O(n) 에 비례해지는 단점이 있다. 단순히 직전과 그 전의 값만 저장하는 방식으로 반복문이나 꼬리재귀 최적화가 된 재귀를 할 경우 시간복잡도 O(n)에 공간복잡도 O(1)도 가능하다. 다만, 정말 큰 임의의 n에 대한 피보나치 수를 구해야한다면, 행렬을 이용하여 시간복잡도 O(log n)에 공간복잡도 O(1)로 구현할 수도 있다. 좀더 높은 레벨의 프로그래밍에서는 피보나치 힙(Fibonacci Heap) 같이 자료구조나 알고리즘 최적화에 피보나치 수열의 성질을 우려먹는 경우를 많이 보게 될 것이다.

자연에서 꽃씨의 배열이나 나무가지의 갈라짐 등등으로 빈번하게 등장하고, 피보나치의 문제처럼 실제 생물의 번식을 설명하는 데에도 쓰인다. 이는 황금비의 자기닮음성이나 프랙탈과도 엮인다.[4] 비슷한 맥락으로 주식시장의 변동을 설명하는 엘리어트 파동 이론(Elliott wave theory) 및 하모닉 패턴(Harmonic Pattern)에서 가장 근간이 되는 개념으로 쓰이기도 하는 등 여러 모로 신기한 수열이다.

베리에이션으로 뤼카 수열(Lucas Sequence)이 있다. 초항과 그 다음 항을 0과 1이 아닌 숫자 두 개를 설정하고 [math( F_{ n + 2 } = F_{ n } + F_{ n + 1 } )]대로 따라가면 뤼카 수열이다.

수학 귀신에도 꽤나 나온다. 번식하는 토끼의 수를 나타내거나 아래에 나오는 두 항의 비율이 황금비에 근접하는 사실 등.

3. 일반항의 유도

피보나치수열의 항의 비율 [math(\displaystyle\frac{F_n}{F_{n-1}})]의 극한값은 소위 황금비가 된다.


위에서 언급한 비네의 식에서 피보나치수열의 일반항을 황금비로 표시할 수 있는데, 황금비를 [math(\varphi)]라고 하고 [math(\varphi'=1-\varphi)] 라고 하면 피보나치수열의 일반항은 다음과 같다.
[math(\displaystyle F_n=\frac{\left(\varphi^{n}-\varphi'{^n}\right)}{\left(\varphi-\varphi'\right)})]
[math(\displaystyle \varphi=\frac{1+\sqrt{5}}{2})]인 무리수인 반면 피보나치수열의 모든 항은 자연수인 걸 감안하면 굉장히 신기한 수열인데, 증명 방법은 대략 다음과 같다.

황금비 [math(\varphi)]는 정의에 따라 [math(x^2-x-1=0)]의 0보다 큰 근이고, 0보다 작은 근은 [math(\varphi')]라고 하자. 그러면 근과 계수와의 관계에서 [math(\varphi+\varphi'=1, \varphi\varphi'=-1)]이다.

이를 이용해 [math(F_n=F_{n-1}+F_{n-2})]를 변형하여 [math(\left(F_n-\varphi F_{n-1}\right)=\varphi'\left(F_{n-1}-\varphi F_{n-2}\right))]과 [math(\left(F_n-\varphi'F_{n-1}\right)=\varphi\left(F_{n-1}-\varphi'F_{n-2}\right))]를 얻는다. 각각에서 [math(F_{n-1}-\varphi F_{n-2})]과 [math(F_{n-1}-\varphi'F_{n-2})]가 등비수열이고 [math(n=3)]일때 각각 [math(1-\varphi=\varphi')]와 [math(1-\varphi'=\varphi)]이다. 이를 이용해 일반항을 구하면 [math(n\geq3)]일 때 [math(F_{n-1}-\varphi F_{n-2}={\varphi'}^{n-2})]이고, [math(F_{n-1}-\varphi'F_{n-2}=\varphi^{n-2})]. 양변을 빼서 정리하면 [math(n\geq3)]일 때 [math(\displaystyle F_{n-2}=\frac{\varphi^{n-2}-{\varphi'}^{n-2}}{\varphi-\varphi'})]이므로 [math(n\geq1)]일 때로 정리하면 위의 식이 나온다.

일반적으로 [math(aZ_{n-2}+bZ_{n-1}+cZ_{n}=0)]의 꼴의 점화식이 주어진다면 [math(ax^2+bx+c=0)]의 두 근을 [math(\alpha, \beta)]라고 했을 때, [math(k\alpha^{n}+l\beta^{n})]의 형태로 일반항이 나오게 된다. [math(k,l)]은 이제 초항 2개를 연립해서 계수를 맞춰넣어서 계산하는데, 초항과 둘째항이 다른 루카스 수열 역시 점화식이 동일하기 때문에 일반항은 계수 [math(k, l)]만 다른 형태로 나오게 되며, 항의 비의 극한값은 여전히 황금비가 나온다.

4. 성질

[math(F_n)]과 [math(F_{n+1})]은 서로소이다.
{{{#!folding [증명]

수학적 귀납법 이용.

주어진 명제에 대하여 [math(F_n)]과 [math(F_{n+1})]은 서로소이다.

[math(n=1)]일 때, 순서쌍 [math((F_1, F_{2}))]의 최대공약수는 1이다.
[math(n=k)]일 때, 순서쌍 [math((F_k, F_{k+1}))]의 최대공약수는 1이라고 가정하자.
[math(n=k+1)]일 때, 순서쌍 [math((F_{k+1}, F_{k+2}))]는 피보나치 수열의 정의에 의하여 [math((F_{k+1}, F_{k+1}+F_k))]로 쓸 수 있다.
순서쌍 [math((F_{k+1}, F_{k+1}+F_k))]의 최대공약수를 구하는 것은, 순서쌍 [math((F_{k+1}, F_k))]의 최대공약수를 구하는 것과 같고, 가정에 의해 최대공약수는 1이다.

따라서 모든 자연수 n에 대해 주어진 명제는 성립한다.
}}}
피보나치 수열의 합: [math(\displaystyle \sum_{k=1}^{n}F_k=F_{n+2}-1)]
{{{#!folding [증명]
[math(F_{n+2}=F_{n+1}+F_n)]은 [math(F_{n+2}-F_{n+1}=F_n)]로 바꾸어 쓸 수 있다.
[math(\displaystyle \sum_{k=1}^{n}F_k=\sum_{k=1}^{n}(F_{k+2}-F_{k+1}))]
[math(=(F_3-F_2)+(F_4-F_3)+...+(F_{n+1}-F_n)+(F_{n+2}-F_{n+1}))]
[math(=F_{n+2}-F_2=F_{n+2}-1)]
}}}


피보나치 수열 제곱의 합: [math(\displaystyle \sum_{k=1}^{n}F_{k}{}^2=F_{n}F_{n+1})]
{{{#!folding [증명]
[math(F_{n+2}=F_{n+1}+F_n)]에 [math(n)] 대신 [math(n-1)]을 대입하면 [math(F_{n+1}=F_{n}+F_{n-1})]. 즉, [math(F_{n}=F_{n+1}-F_{n-1})]이다.
[math(\displaystyle \sum_{k=1}^{n}F_{k}{}^2=F_1{}^2+\sum_{k=2}^{n}F_{k}F_{k}=F_1{}^2+\sum_{k=2}^{n}F_{k}(F_{k+1}-F_{k-1})=F_1{}^2+\sum_{k=2}^{n}(F_{k}F_{k+1}-F_kF_{k-1}))]
[math(=F_1{}^2+(F_3F_2-F_2F_1)+(F_4F_3-F_3F_2)+...+(F_{n+1}F_n-F_nF_{n-1}))]
[math(=F_{n+1}F_n+F_1{}^2-F_2F_1=F_nF_{n+1}+1-1=F_nF_{n+1})]
}}}
피보나치 수열 분수의 합: [math(\displaystyle \sum_{k=1}^{n} \dfrac {F_k}{F_{k+1}F_{k+2}}=\dfrac 1{F_2}-\dfrac 1{F_{n+2}})]
{{{#!folding [증명]
[math(\displaystyle \sum_{k=1}^{n} \dfrac {F_k}{F_{k+1}F_{k+2}}=\sum_{k=1}^{n} \dfrac {F_k}{F_{k+2}-F_{k+1}}(\dfrac 1{F_{k+1}}-\dfrac 1{F_{k+2}})=\sum_{k=1}^{n} \dfrac {F_{k+2}-F_{k+1}}{F_{k+2}-F_{k+1}}(\dfrac 1{F_{k+1}}-\dfrac 1{F_{k+2}}))]
[math(=\displaystyle \sum_{k=1}^{n}(\dfrac 1{F_{k+1}}-\dfrac 1{F_{k+2}})=(\dfrac 1{F_2}-\dfrac 1{F_3})+(\dfrac 1{F_3}-\dfrac 1{F_4})+...+(\dfrac 1{F_{n+1}}-\dfrac 1{F_{n+2}}))]
[math(=\dfrac 1{F_2}-\dfrac 1{F_{n+2}})]
}}}
다항식 [math(x^n)]을 [math(x^2-x-1)]로 나눈 나머지를 [math(a_nx+b_n)]이라 하면, 수열 [math(\{a_n\})]은 피보나치 수열이다.
{{{#!folding [증명]
[math(x^n)]을 [math(x^2-x-1)]로 나눈 몫을 [math(Q(x))]라 하면 다음과 같이 쓸 수 있다.

[math(x^n=(x^2-x-1)Q(x)+a_nx+b_n\quad\cdots①)]

이때, 방정식 [math(x^2-x-1=0)]의 두 근을 [math(\alpha)], [math(\beta)]라 하면

[math(\alpha^2-\alpha=\beta^2-\beta=1\cdots②)]

이고 이차방정식의 근과 계수의 관계에 의하여

[math(\alpha+\beta=1,\,\alpha\beta=-1\cdots③)]

①에 [math(x=\alpha)], [math(x=\beta)]를 대입하여 두 식의 차를 구하면

[math(\begin{aligned}\alpha^n&=a_n\alpha+b_n\\\beta^n&=a_n\beta+b_n\\\hline\alpha^n-\beta^n&=a_n(\alpha-\beta)\\\therefore a_n&=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}\end{aligned})]

그러면 ③에 따라 처음 두 항은

[math(\begin{aligned}a_1&=\dfrac{\alpha-\beta}{\alpha-\beta}=1\\a_2&=\dfrac{\alpha^2-\beta^2}{\alpha-\beta}=\alpha+\beta=1\end{aligned})]

이고, ②에 따라 다음이 성립한다.

[math(\begin{aligned}a_n+a_{n+1}&=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}+\dfrac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}\\&=\dfrac{\alpha^n(1+\alpha)-\beta^n(1+\beta)}{\alpha-\beta}\\&=\dfrac{\alpha^{n+2}-\beta^{n+2}}{\alpha-\beta}=a_{n+2}\end{aligned})]

결론적으로 [math(a_1=a_2=1)], [math(a_{n+2}=a_n+a_{n+1})]임이 증명되었다.}}}

5. 음의 피보나치 수열

[math(F_0=0)]
[math(F_1=1)]
[math(F_n=F_{n-1}+F_{n-2})]
이 식에서 n의 범위를 정수로 확장하면 [math(F_{-1})]를 비롯해서 음의 피보나치 수를 구할 수 있다.
[math(F_0=0)]
[math(F_{-1}=1)]
[math(F_{-2}=-1)]
[math(F_{-3}=2)]
[math(F_{-4}=-3)]
피보나치 수열에서 2번에 1번씩 번갈아 부호가 음수가 되는 수열이 만들어진다.
(0), 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987
즉, 적당한 [math(k, \ \left(k>0\right))]에 대해서 [math(F_{-k})]는 다음을 만족시킨다.
[math(F_{-k}=\left(-1\right)^{k+1}F_k)]


6. 유리수에서

[math(\dfrac 1 {1000000 - 1000 - 1} = \dfrac{1}{998999})]을 소수로 나타내면

[math(0.000\red {001}001\red {002}003\red {005}008\red {013}021\red {034}055\red {089}144 \red{233}377...)]로 각 세자리 마다 피보나치 수가 나타난다.

이를 일반화하여 n자리마다 피보나치 수가 나타나는 유리수를 만들 수가 있다.[5]
[math(\dfrac 1 {10^{2n} - 10^n - 1} = \displaystyle\sum^\infty_{k = 0} \dfrac {F_{k}} {10^{n(k - 1)}})]
증명

7. 활용

7.1. 경우의 수

피보나치 수는 계단을 오르는 경우의 수로 생각할 수 있다. 계단을 오를 때 한 번에 한 계단 또는 두 계단을 오를 수 있다면, 계단 [math(n)]개를 오르는 경우의 수는 [math(F_{n+1})]이다. 이를 증명하여 보자.

파일:계단 오르는 경우의 수 2.png
먼저, 계단 [math(1)]개를 오르는 경우의 수는 당연히 [math(1)]이고, 계단 [math(2)]개를 오르는 경우의 수는 한 계단씩 두 번 오르는 경우와 두 계단을 한 번 오르는 경우 이렇게 두 가지이다.

파일:계단 오르는 경우의 수 1.png
위 그림과 같이, 계단 [math(n)]개를 오르는 경우의 수는 마지막에 한 계단을 오르는 경우와 마지막에 두 계단을 오르는 경우로 나누어 구할 수 있다.[6] 전자는 마지막의 한 계단을 제외한 계단 [math((n-1))]개를 오르는 경우의 수가 되고, 후자는 마지막의 두 계단을 제외한 계단 [math((n-2))]개를 오르는 경우의 수가 된다.

원래 피보나치 수열은 [math(1,\,1,\,2,\,3,\,5\cdots)]인데, 계단을 오르는 경우의 수는 처음 두 항이 [math(\boldsymbol{1,\,2})]인 피보나치 수열이 되므로 계단 [math(n)]개를 오르는 경우의 수는 [math(F_n)]이 아닌 [math(F_{n+1})]이 된다.

8. 알고리즘

팩토리얼이 그렇듯, 피보나치 수열의 n번째 항을 구하는 알고리즘도 반복과 재귀 두 가지 형식으로 구현할 수 있다.
  • 반복문 형태의 알고리즘
#!syntax cpp
unsigned int fibonacci_iter(unsigned int n) {

    if (n <= 1) return n; // n이 1보다 작을 때는 해당 값을 그대로 반환한다.
    else {

        int result = 0;
        int iterA = 0, iterB = 1;

        for (int i = 2; i <= n; i++) {

            result = iterA + iterB;
            iterA = iterB;
            iterB = result;

        } // n항의 값을 구한다.

        return result;

    }
	
}

  • 재귀 형태의 알고리즘
#!syntax cpp
unsigned int fibonacci_rcsv(unsigned int n) {

    if (n <= 1) return n; // n이 1보다 작을 때는 해당 값을 그대로 반환한다.
    else return fibonacci_rcsv(n - 2) + fibonacci_rcsv(n - 1);
	
}


단, 위와 같이 단순하게 재귀 알고리즘으로 구현하는 경우는, 불필요하게 같은 값을 다시 계산하게 되어 계산 속도가 엄청 느리다. 실제로 구현할 때는 한 번 계산한 값을 저장해 두고, 재계산하지 않는 메모이제이션 기법을 사용하여 구현해야 한다.

또한, 어떤 알고리즘인지와 무관하게, 피보나치 수열의 값은 상당히 급격하게 증가하므로 오버플로에 유의해야 한다. F(48) = 4807526976 으로 32비트 unsigned int 의 최댓값을 넘어간다. 심지어 64비트 unsigned long long 타입을 쓰더라도 F(94) = 19740274219868223167 는 LLONG_MAX = 18446744073709551615 보다 커서 오버플로가 발생한다. 정말 큰 수의 피보나치 수열의 값을 계산하려면, 이를 처리할 수 있는 BigInt 라이브러리 등을 써야 한다.

8.1. 분할 정복을 이용한 알고리즘 [math(\mathcal{O}(\log n) )]

피보나치 수로 이루어진 2x2 행렬 [math(\begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix})]를 생각하자. 이 행렬에 [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix})]를 곱하면,

[math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix} \begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix} = \begin{pmatrix} 1F_{n+1}+1F_n&1F_n+1F_{n-1} \\ 1F_{n+1}+0F_{n}&1F_n+0F_{n-1} \end{pmatrix} = \begin{pmatrix} F_{n+2}&F_{n+1} \\ F_{n+1} &F_{n} \end{pmatrix})]

를 얻는다.

또한 [math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix} = \begin{pmatrix} F_{2}&F_{1} \\ F_{1} &F_{0} \end{pmatrix})]이다.

따라서 다음과 같은 일반화된 공식을 얻을 수 있다:

[math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix})]


[math(\begin{pmatrix} 1&1\\1&0 \end{pmatrix})]를 [math(M)]이라고 하자. [math(M)]을 n-1번 거듭제곱하면 [math(F_n)]을 얻을 수 있다.[7] 그러나 단순히 이를 n-1번 곱하는 방식은 시간 복잡도가 위의 반복문을 이용한 방식과 동일한 [math(\mathcal{O}(n))]이다. 그러나, [math({M}^{n} {M}^{m} = {M}^{n+m})] 라는 점을 이용하면 이를 [math(\mathcal{O}(\log n) )]으로 줄일 수 있다.

모든 양의 정수는, 2의 제곱수들을 각각 한 번 이하로 더하여 만들 수 있다. 이 사실이 2진법의 작동 배경이며, 어떤 양의 정수의 2진법 표기에서 i번째 자리수가 의미하는 바는, 해당 정수를 만들기 위해 [math(2^i)]를 몇 번 더해야 하는지이다. 예를 들어, 100과 43을 2진법으로 나타내면 1100100, 101011인데, 이는
[math(100 = 1100100_2 = 1 \times 2^6+1 \times 2^5+0 \times 2^4+0 \times 2^3+1 \times 2^2+0 \times2^1+0 \times 2^0 = 64+32+4)],
[math(43 = 101011_2 = 1 \times 2^5+0 \times 2^4+1 \times 2^3+0 \times 2^2+1 \times 2^1+1 \times 2^0 = 32+8+2+1)]임을 의미한다.

이 사실이 시사하는 바는, 어떤 양의 정수 n의 2진법 표현을 알고 있다면, [math(M)]를 2의 제곱수들만큼 제곱하여 얻은 일련의 행렬들[math(\{M^1, M^2, M^4, M^8, M^{16}, M^{2^5}, M^{2^6} ...\})][8]을 하나의 단위행렬에다가 각각 한 번 혹은 0번 곱하여 [math(M^n)]을 구할 수 있다는 것이다. [9]


이를 이용해, 양의 정수 n을 입력받아 [math(F_n)]을 구하는 다음과 같은 알고리즘을 만들 수 있다:
  • n-1의 이진법 표기의 각각 자리수들을 역순으로 나열한 배열 binarr을 만든다. [10]
  • [math(M^{2^i})]의 값들을 담을 빈 동적 배열 m_powers를 만든 후, 첫 번째 자리에 [math(M)]을 넣는다.
  • m_powers의 맨 뒤에 m_powers[-1][11]의 제곱을 추가하는 작업을, m_powers의 길이가 binarr의 길이와 같아질 때까지 반복한다. 이 작업이 완료되면, binarr[i]는 [math(M^{n-1})]을 만들기 위해 m_powers[i]가 곱해져야 할 지의 여부를 나타내게 된다.
  • 2x2 단위행렬 final_mat를 만든다.
  • 정수 i가 0에서 len(binarr)-1이 될 때까지 1만큼 증가시키며, 다음을 반복한다:
    • 만약 binarr[i] == 1이라면, final_mat에 m_powers[i]를 곱한다.
  • final_mat[0][0]이 [math(F_n)]이다.
#!syntax python
from math import log2

def matmul_2x2(a, b):
    # 2x2 행렬 곱셈
    return_mat = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                return_mat[i][j] += a[i][k] * b[k][j]
    
    return return_mat

def to_reverse_bin(n: int):
    return_array = [0 for _ in range(int(log2(n))+1)]
    while n > 0:
        temp_lg2n = int(log2(n))
        return_array[temp_lg2n] += 1
        n -= 2 ** temp_lg2n
    
    return return_array

def fib(n: int):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    binarr = to_reverse_bin(n-1) 
    # 또는 python의 내장 라이브러리 함수 bin()을 이용하여
    # binarr = list(map(int, reversed(bin(n-1)[2:])))

    m_powers = []
    m_powers.append(
        [[1, 1],
        [1, 0]]
    )

    for i in range(1, len(binarr)):
        m_powers.append(matmul_2x2(m_powers[-1], m_powers[-1]))
    
    final_mat = [
        [1, 0],
        [0, 1]
    ]
    for i in range(len(binarr)):
        if binarr[i]:
            final_mat = matmul_2x2(m_powers[i], final_mat)

    return final_mat[0][0]

if __name__ == "__main__":
    print(fib(1000000))

9. 여담

  • 치킨과의 상관관계
    인터넷 상에서 피보나치 수열이 치킨수([math(F_{n-1})])와 먹을 사람수([math(F_n)])와의 관계를 나타내는데 적절하다는 설이 있다. 이는 한 사람이 여유있게 먹을 수 있는 치킨의 양이 1인분에 약간 못 미치며, 한 마리를 다 뜯기에는 배부르기 때문이다.[12]1인1닭이 가능한 사람들이라면 굳이 신경쓸 필요 없다.
서울대학교 대나무숲 페이지에는 먹을 사람 수가 정확히 피보나치 수열의 [math(F_n)]이 되지 않을 때, 치킨도르프제켄도르프(Zeckendorf)의 정리를 이용하면 비교적 적절한 양의 치킨을 알 수 있다고 소개하고 있다.
피보나치킨 수를 구하는 알고리즘은 간단하지 않다. 임의의 자연수 N에 대해서 제켄도르프의 정리를 이용하여 피보나치 수로 분해하여야 하고, 분해된 피보나치 수의 이전 항을 구해야 하기 때문이다. 하지만 피보나치킨 수를 구하는 알고리즘을 진지하게 연구하여 아래와 같은 최적의 알고리즘을 구현한 유튜버도 있다. [13]
#!syntax python
def FibonaChicken(N):
    if N <= 2:
        return 1
    i = inverse_fibonacci(N)
    if is_fibonacci(N):
        return Binet(i - 1)
    else:
        while N > Binet(i):
            i += 1
        return Binet(i - 2) + FibonaChicken(N - Binet(i - 1))


피보나치 수열의 숫자들로 이루어지는 기울기는 눈으로 봐서는 큰 차이가 나지 않기 때문에 이 숫자들의 길이를 가진 도형을 조합해 눈속임을 하는 것이 가능하다. 대표적으로 가로 세로 8짜리 정사각형을 피보나치 수에 맞춰 나눈 다음 조립해 가로 13, 세로 5짜리인 직사각형을 만들어 1만큼의 면적을 늘리는 트릭이 있다. 실제로 64짜리 정사각형을 쪼개 65짜리 직사각형을 만들어보면 대각선쪽이 약간 벌어져 있다는 것을 알수 있으며 캐드 등을 이용해보면 이 벌어진 공간의 면적이 정확히 1이라는 것도 알 수 있다. #

10. 관련 문서



[1] 피보나치 수열에 등장하는 소수 [2] 다만, 어떤 [math(n)] 값에 대하여 [math(F_n)]이 소수라면, 그 [math(n)] 값은 단 하나의 예외인 [math(n=4)]를 제외하면 모두 홀수인 소수라는건 증명되어 있다. [3] 아랍 문명에서 표준화 되어있던 아라비아 숫자 체계의 계산법을 공부하여 유럽에 소개한 사람이 바로 피보나치이다. [4] 다만 이것이 와전되어 황금비를 유사과학적으로 접근하는 사람들이 생겨났다. [5] 다만, 100-10-1=89 등 작은 분모를 가진 분수에서는 수가 겹치기 때문에 금방 규칙성이 사라진다. [6] 혹은 처음에 한 계단을 오르는 경우와 처음에 두 계단을 오르는 경우로 나눌 수도 있다. [7] 참고로 이는 음수에서도 성립한다. [math(\begin{pmatrix}1&1\\1&0\end{pmatrix}^{-1}=\begin{pmatrix}0&1\\1&-1\end{pmatrix})]이므로 [math(n)]이 음수일 때는 이를 거듭제곱해 구할 수 있다. 물론 앞에서 본 성질을 이용해도 된다. [8] [math(M^mM^m=M^{2m})]이므로, [math(M)]을 제곱하여 [math(M^2)]를 얻고, [math(M^2)]를 제곱하여 [math(M^4)]를 얻고, 또 [math(M^4)]를 제곱하여 [math(M^8)]을 얻는 식으로 차례대로 구할 수 있다. [9] 예를 들어,
[math(M^{100} = M^{64}M^{32}M^{4}I)],
[math(M^{43} = M^{32}M^{8}M^2M^1I)]
이런 식이다.
[10] n-1이 43이라면, 만들어지는 binarr은 {1, 1, 0, 1, 0, 1}이다. [11] 기존의 맨 마지막 원소 [12] 박부성 교수의 설명에 의하면 음식점에서 1인분을 정량대로 주었다가 고객이 남기면 음식점 입장에선 손해이므로 실제로는 조금 적은 0.6인분 정도의 양을 주는데, 바꿔말하면 1명당 약 1.6인분을 시켜야 적당하고 피보나치 수열이 약 1.618배씩 커지기 때문이라고 한다. [13] 피보나치 수와 황금비: 쓸데없이 고퀄인 피보나치킨 알고리즘 TMI 연구