Szybka rekurencja modularna

Wpisany przez Rafał Świetlicki, 11 stycznia 2007 09:58

Niech x, y będą dowolnymi liczbami całkowitymi, a, b dowolnymi liczbami całkowitymi różnymi od zera, m – liczbą całkowitą większą niż 1.
Załóżmy, że dany jest ciąg liczb całkowitych zdefiniowany rekurencyjnie:

G_0 = x\\ G_1 = y\\ G_n = aG_{n-2} + bG_{n-1} \text{, gdzie} n \geq 2

Interesuje nas obliczenie G_n mod m dla ustalonej liczby n.
Przyjmując np. x = y = a = b = 1, m = 10 jako G_n mod m dostaniemy ostatnią cyfrę n – tej liczby Fibonacciego.

Algorytm polegający na wyznaczaniu kolejnych wyrazów G_k mod m dla k = 2, 3, ..., n ma złożoność O(n) i dla bardzo dużych wartości n jest niepraktyczny. Można to zrobić o wiele szybciej w czasie O(log n) wykorzystując działania na macierzach oraz szybkie potęgowanie modularne.
Korzystając z indukcji matematycznej łatwo udowodnić następującą tożsamość:

G_n = [a,b] \begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix}^{n-2} \begin{bmatrix} G_0\\ G_1\\ \end{bmatrix}, n \geq 2

Ze wzoru tego wynika, że należy najpierw obliczyć:

\begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix}^{n-2} \mod m

Potęgowanie macierzy odbywa się podobnie jak potęgowanie liczby opisane w artykule szybkie potęgowanie modularne. Jeżeli liczby a i/lub b są niemniejsze niż m to najpierw w macierzy, którą będziemy potęgować zastępujemy te liczby ich resztami z dzielenia przez m. Wprowadzamy macierz pomocniczą X o dwóch wierszach i dwóch kolumnach, która na początku będzie równa macierzy jednostkowej. Dalej, wyznaczamy kolejne cyfry rozwinięcia dwójkowego liczby n – 2. W każdym kroku (których ilość jest równa liczbie cyfr dwójkowych liczby n – 2), przemnażamy macierz X przez samą siebie a wynik mnożenia ponownie przypisujemy pod macierz X. Dodatkowo, jeżeli kolejna cyfra dwójkowa liczby n – 2 (licząc od cyfry najwyższego rzędu) jest równa 1, macierz:

\begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix}

przemnażamy przez macierz X
Na koniec każdy z czterech elementów macierzy X zastępujemy jego resztą z dzielenia przez m.

Ponieważ cyfry dwójkowe liczby n – 2 pobierane są od cyfry najwyższego rzędu, zatem najprościej potęgowanie macierzy modulo m zrealizować rekursywnie tak, jak zostało to wykonane w dołączonej implementacji algorytmu.

Ostatecznie przyjmując:

\begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix}^{n-2} \mod m = \begin{bmatrix} p & q\\ r & s\\ \end{bmatrix}

Otrzymujemy:

G_n \mod m = [ap + br, aq + bs] \begin{bmatrix} G_0\\ G_1\\ \end{bmatrix} \mod m =\\ (G_0(ap+br) + G_1(aq+bs)) \mod m

Dowod poprawności algorytmu (Adam Mika):

G_n = aG_{n-2} + bG_{n-1} = [a,b] \begin{bmatrix} G_{n-2}\\ G_{n-1}\\ \end{bmatrix} =\\ [a,b] \begin{bmatrix} 0*G_{n-3}+1*G_{n-2}\\ a*G_{n-3}+b*G_{n-2}\\ \end{bmatrix} =\\ [a,b] \begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix} \begin{bmatrix} G_{n-3}\\ G_{n-2}\\ \end{bmatrix} =\\ [a,b] \begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix}^2 \begin{bmatrix} G_{n-4}\\ G_{n-3}\\ \end{bmatrix} =\\ ...\\ [a,b] \begin{bmatrix} 0 & 1\\ a & b\\ \end{bmatrix}^{n-2} \begin{bmatrix} G_{0}\\ G_{1}\\ \end{bmatrix}

Implementacje

Autor	Język programowania	Komentarz	Otwórz	Pobierz	Ocena
Tomasz Lubiński	Ada		.ada	.ada	***** / 1
Tomasz Lubiński	C#	MS Visual Studio .net	.cs	.cs	***** / 1
Rafał Świetlicki	C/C++		.cpp	.cpp	***** / 1
Dawid Drozd	C/C++		.cpp	.cpp	***** / 2
Jan Wojciechowski	C/C++	C++ templates	.cpp	.cpp	***** / 0
Tomasz Lubiński	Delphi/Pascal		.pas	.pas	***** / 1
Rafał Świetlicki	Java		.java	.java	***** / 2
Marek Rynarzewski	Php		.php	.php	***** / 0

Poprawiony: 04 października 2012 19:01

Dodaj komentarz

JComments


Dodaj własną implementację tego algorytmu
Zaloguj się na stronie
Plik:
Język programowania:
Komentarz:
	By móc dodać implementacje zaloguj się na stronie