System resztowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ten artykuł dotyczy systemu liczbowego. Zobacz też: arytmetyka resztowa liczb całkowitych.

System resztowy (skr. RNS od ang. residue number system) – system liczbowy służący do reprezentacji liczb całkowitych wektorem reszt z dzielenia względem ustalonego wektora wzajemnie względnie pierwszych modułów. Chińskie twierdzenie o resztach orzeka, że taka reprezentacja jest jednoznaczna dla liczb całkowitych ze zbioru [0, M), gdzie M jest iloczynem wszystkich modułów.

Niech B = (m1, m2, ..., mn), będzie bazą względnie pierwszych modułów, a M ich iloczynem. Wtedy reprezentacją liczby X w systemie resztowym o bazie B jest (x1, x2, ..., xn) gdzie xi = X mod mi dla każdego 1 ≤ in.

Operacje[edytuj]

Na liczbach reprezentowanych w systemie resztowym może być efektywnie przeprowadzonych wiele operacji arytmetycznych. Wykonuje się je przeprowadzając niezależnie na odpowiednich resztach 'zwykłe' operacje, a następnie operację modulo odpowiedniego modułu. Dla następujących operacji rozważmy dwie liczby całkowite, A i B, reprezentowane przez ai i bi w systemie resztowym zdefiniowanym przez bazę mi (dla i z przedziału 0 ≤ in).

Dodawanie i odejmowanie[edytuj]

Dodawanie (lub odejmowanie) może być wykonane przez proste dodawanie (lub odejmowanie) małych liczb całkowitych i policzenie odpowiedniego modułu:

może być policzone w systemie resztowym jako:

Mnożenie[edytuj]

Mnożenie można wykonać w podobny sposób do dodawania i odejmowania. Aby obliczyć:

liczymy:

Przykład[edytuj]

Przyjmijmy bazę (2,3,5). Rozpatrzmy dwie liczby, X=2 i Y=23. W przyjętym systemie resztowym liczby te reprezentujemy jako X = (0,2,2), Y= (1,2,3). :

Obliczamy wartość iloczynu przy użyciu systemu resztowego:

(0, 2, 2) * (1, 2, 3) = (0*1 mod 2, 2*2 mod 3, 2*3 mod 5) = (0, 1, 1)

Liczba (0, 1, 1) po zamianie na liczbę całkowitą w reprezentacji dziesiętnej wynosi 16.

Dzielenie[edytuj]

Dzielenie w systemie resztowym jest bardziej skomplikowanie.

Z drugiej strony jeśli B jest liczbą pierwszą dla M (tzn. dla wszystkich i) wtedy

może być prosto policzone przez

gdzie jest liczbą odwrotną do B modulo M, i jest liczbą odwrotną z modulo (współczynniki mogą zostać wyliczone raz dla danego systemu resztowego).

Konwersja odwrotna[edytuj]

Konwersję odwrotną można przeprowadzić w następujący sposób. Niech (x1, x2, ..., xn) będzie reprezentacją liczby X w systemie resztowym o bazie (m1, m2, ..., mn), oraz niech

oraz

gdzie

;

wtedy

Np. w systemie o bazie (3, 5, 7), reprezentacją X jest (2, 3, 4), wtedy

oraz

więc

Zobacz też[edytuj]

Linki zewnętrzne[edytuj]

  • [1] – artykuł opisujący jeden z możliwych algorytmów dzielenia