algorytm.org

Szybka rekurencja modularna

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szybka rekurencja modularna
Ocena użytkowników:***** / 4
SłabyŚwietny 
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 Gn mod m dla ustalonej liczby n.
Przyjmując np. x = y = a = b = 1, m = 10 jako Gn mod m dostaniemy ostatnią cyfrę n – tej liczby Fibonacciego.

Algorytm polegający na wyznaczaniu kolejnych wyrazów Gk 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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 1
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 1
Rafał ŚwietlickiC/C++
.cpp
.cpp
***** / 1
Dawid DrozdC/C++
.cpp
.cpp
***** / 1
Jan WojciechowskiC/C++C++ templates
.cpp
.cpp
***** / 0
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Rafał ŚwietlickiJava
.java
.java
***** / 2
Marek RynarzewskiPhp
.php
.php
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 04 października 2012 19:01
Dodaj komentarz