피보나치 수열

피보나치 수열은 앞의 두 숫자를 더한 것이 다음 항이 된다는 수열로 다음의 점화식으로 정의됩니다.

F_0 = 0, \\
F_1 = 1, \\
F_{n+2} = F_n + F_{n+1} (n ≥ 0)

실제로는 다음과 같은
수치가 됩니다(제0~21항)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,

계산 방법

앞 두 개의 숫자를 기억해두면 되므로 항의 작은 쪽에서 계산하면 쉽게 계산할 수 있습니다.

행렬 누승

항의 작은 쪽으로부터 계산하는 경우는 제N항을 구하기 위해서 $O(N)$ 걸립니다만 행렬 누승이라고 하는 생각을 이용하면 $O(logN)$로 구해집니다.

조금 견해를 바꾸어 피보나치 수열을 다음과 같은 천이라고 생각해 보겠습니다 (그림의 화살표는 가산입니다).
하고 있는 일은 아무것도 변함없이 필요한 상태를 세로로 늘어놓게 했습니다


이런 식으로 잘 행렬의 표현식으로 떨어질 수 있습니다.
구체적으로는 다음과 같은 식입니다.

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} 
\begin{pmatrix}
F_{n+1} \\ F_{n}
\end{pmatrix} = 
\begin{pmatrix}
F_{n + 1} + F_{n}\\ F_{n+1}
\end{pmatrix} 
=
\begin{pmatrix}
F_{n + 2} \\ F_{n+1}
\end{pmatrix} 

이것을 바탕으로 2항처는 다음과 같이 표현할 수 있습니다(행렬은 교환칙은 채우지 않지만 결합칙은 만족하므로 원하는 순서로 계산할 수 있습니다)

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} 
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} 
\begin{pmatrix}
F_{n+1} \\ F_{n}
\end{pmatrix} = 
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} 
\begin{pmatrix}
F_{n + 2} \\ F_{n+1}
\end{pmatrix} =
\begin{pmatrix}
F_{n + 3} \\ F_{n+2}
\end{pmatrix} 

여기서 행렬의 n승을 구하기 위해 반복 제곱법을 사용하면 $O(logN)$로 계산할 수 있다는 것입니다.
※실제로는 행렬의 사이즈를 M × M로 할 때 $O(M^3logN)$입니다.

그렇다면 n에 0을 대입하고 m 항선을 계산하는 경우 다음과 같이 표현할 수 있습니다.

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{m}
\begin{pmatrix}
F_{1} \\ F_{0}
\end{pmatrix} =
\begin{pmatrix}
F_{m + 1} \\ F_m
\end{pmatrix}

구체적인 예

예를 들어 제8항을 계산해 보겠습니다.

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{8}
\begin{pmatrix}
F_{1} \\ F_{0}
\end{pmatrix} =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{2^{3}}
\begin{pmatrix}
1 \\ 0
\end{pmatrix}\\
= \begin{pmatrix}
2 & 1 \\
1 & 1
\end{pmatrix}^{2^{2}}
\begin{pmatrix}
1 \\ 0
\end{pmatrix}\\
= \begin{pmatrix}
5 & 3 \\
3 & 2
\end{pmatrix}^{2}
\begin{pmatrix}
1 \\ 0
\end{pmatrix}\\
= \begin{pmatrix}
34 & 21 \\
21 & 13
\end{pmatrix}
\begin{pmatrix}
1 \\ 0
\end{pmatrix}\\
=
\begin{pmatrix}
34 \\ 21
\end{pmatrix}\\

라는 느낌입니다.
제8항은 21, 제9항은 34이므로 올바르게 계산할 수 있을 것 같습니다.