Przy koszcie pamięciowym rzędu \(\displaystyle{ \mathcal{O}(\log n)}\) i jakiś tam modyfikacjach może pewnie działać w czasie \(\displaystyle{ \mathcal{O}(\log n)}\), ale szkoda zachodu. Albo zostawić koszt liniowy, albo poświęcić 5 minut na opanowanie potęgowania macierzy. Wcale nie trzeba rozumieć macierzy. Wystarczy rozumieć mnożenie macierzy i iterowany kwadrat, a to bardzo elementarne. Mam teraz nieco więcej czasu więc może coś dopiszę:
Idea jest następująca, jeśli \(\displaystyle{ A}\) jest tą macierzą opisującą ciąg Fibonacciego to, jak to wypisał Zordon, wystarczy poznać wartość \(\displaystyle{ A^n}\), żeby otrzymać \(\displaystyle{ F_{n+1}}\). Zapiszmy pomocniczo liczbę \(\displaystyle{ n}\) w systemie dwójkowym, czyli przedstawmy ją w postaci:
\(\displaystyle{ n=\sum a_i2^i}\). Powiedzmy, że otrzymaliśmy \(\displaystyle{ \color{red}11101}\).
Wówczas
\(\displaystyle{ A^n=A^{\begin{color}{red}1\end{color}\cdot 2^4}\cdot A^{\begin{color}{red}1\end{color}\cdot 2^3}\cdot A^{\begin{color}{red}1\end{color}\cdot 2^2}\cdot A^{\begin{color}{red}0\end{color}\cdot 2^1}\cdot A^{\begin{color}{red}1\end{color}\cdot 2^0}}\)
i widzimy, że wystarczy czterokrotnie (a w ogólności \(\displaystyle{ \mathcal{O}(\log n)}\) krotnie) podnieść jakąś potęgę \(\displaystyle{ A}\) do kwadratu, żeby otrzymać wszystkie czynniki w iloczynie powyżej.
Stąd algorytm podnoszenia \(\displaystyle{ A}\) do potęgi \(\displaystyle{ n}\)-tej w "pseudo C":
Input: \(\displaystyle{ n, A=\begin{pmatrix}1&1\\1&0\end{pmatrix}}\)
Output: \(\displaystyle{ A^n}\)
\(\displaystyle{ E}\) to macierz jednostkowa, czyli w przypadku \(\displaystyle{ 2\times 2}\) macierz \(\displaystyle{ \begin{pmatrix}1&0\\0&1\end{pmatrix}}\)
Kod: Zaznacz cały
long F(long n, matrix A){
X = E;
Y = A;
i = n;
while (i > 0){
if (i % 2) X = X * Y;
Y = Y^2;
i = floor(i/2);
};
return X;}Działający kod w Matlabie. Matlab nie rozróżnia mnożenia macierzy od mnożenia liczb (zbrodnią jest kodowanie macierzy w innym środowisku), więc jest krótko:
Kod: Zaznacz cały
M=10^9+7;
E=[1,0;0,1];
A=[1,1;1,0];
X = E;
Y = A;
i = n;
while (i > 0){
if mod(i,2) X = mod(X * Y,M);
end;
Y = mod(Y^2,M);
i = floor(i/2);
end;