algorytm.org

Rozszerzony algorytm Euklidesa

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?

Rozszerzony algorytm Euklidesa
Ocena użytkowników:***** / 34
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 25 kwietnia 2006 21:29

Największy wspólny dzielnik dwóch liczb może być przedstawiony w postaci kombinacji liniowej tych liczb ze współczynnikami całkowitymi:
NWD(a, b) = x*a + y*b
przy czym zarówno NWD jak i liczby x oraz y można znaleźć w czasie O(ln2(a)).
I właśnie do znalezienia takiej kombinacji liniowej służyć może przedstawiony tutaj rozszerzony algorytm Euklidesa.

Ponadto algorytm ten może być użyty do znalezienia liczby odwrotnej do b mod a
Liczba odwrotna do liczby b mod a jest to liczba y spełniającą równanie:
b * y mod a = 1
co zapisuje się jako
b * y ≡ 1 (mod a)
przy czym liczbę odwrotną b mod a można znaleźć również w czasie O(ln2(a)). Liczba ta jednak istnieje, jeżeli NWD(a, b)=1.

Algorytm przebiega następująco (zakładamy, że a>b):

Przypiszmy początkowe wartości:
q = Floor(a/b) - cześć całkowita z dzielenia a/b
r = a - q*b - reszta z dzielenia a/b
nwd = b - początkowa wartość wyniku, gdyby już teraz reszta wynosiła 0

Zainicjuj pomocnicze zmienne do obliczenia wartości dla kombinacji liniowej i odwrotności b mod a
xi-2 = 1
xi-1 = 0
xi = 1
yi-2 = 0
yi-1 = 1
yi = (q-1) - początkowa wartość wyniku, gdyby już teraz reszta wynosiła 0.

Dopóki reszta r jest różna od zera wykonuj następujące kroki (i - oznacza numer iteracji, zainicjowane początkowo wartosci xi oraz yi zostają nadpisane podczas pierwszej iteracji):
  a = b
  b = r
  xi = xi-2 - q*xi-1
  yi = yi-2 - q*yi-1
  i = i + 1
  nwd = r
  q = Floor(a/b); - cześć całkowita z dzielenia a/b
  r = a - q*b - reszta z dzielenia a/b

Zwróć uwagę, że w trakcie obliczeń potrzebne są tylko 3 wartości x oraz y, z bieżącej iteracji, poprzedniej i przedpoprzedniej. Nie trzeba zatem tworzyć tablicy a wystarczą jedynie 3 zmienne.
Jeżeli reszta wynosi 0 to, wówczas wynik przechowywany jest w zmiennej nwd
Współczynniki kombinacji liniowej przechowywane są w zmiennych xi oraz yi, oryginalne wartości a oraz b zostały zniszczone podczas prowadzenia obliczeń więc należy je zapamiętać przed przeprowadzeniem obliczeń.
Ponadto jeżeli NWD(a, b) = 1, to liczba odwrotna do liczby b mod a jest przechowywana w zmiennej yi.

Przykłady

a = 6
b = 3
iabqrnwdxixi-1xi-2yiyi-1 yi-2
163203101-110

NWD(6, 3) = 3 = 1 * 6 + -1 * 3

a = 84
b = 15
iabqrnwdxixi-1xi-2yiyi-1 yi-2
184155915101-410
1159169101-510
296136-1106-51
3632032-11-116-5

NWD(84, 15) = 3 = 2 * 84 + -11 * 15

a = 26
b = 15
iabqrnwdxixi-1xi-2yiyi-1 yi-2
1261511115101010
115111411101-110
2114234-1102-11
3431133-11-52-1
431301-43-17-52

NWD(26, 15) = 1 = -4 * 26 + 7 * 15
15 * 7 mod 26 = 1

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 6
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 6
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 9
Emil HotkowskiC/C++rekurencyjny
.cpp
.cpp
***** / 0
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 12
Tomasz LubińskiJava
.java
.java
***** / 6
 
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: 28 października 2012 15:29
Komentarze
photo
-4 # aga 2011-06-02 13:38
świetny opis, bardzo pomocny.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz

Kod antysapmowy Odśwież