Algorytm

Przykład 1.

Wyznacz największy wspólny dzielnik liczb 282 i 78.

Rozwiązanie:

Zaczynamy od podzielenia liczby 282 przez liczbę 78 z resztą:

282:78=3, reszty 48

Otrzymaliśmy resztę różną od zera, zatem teraz podzielimy liczbę 78 przez resztę 48. Ten schemat będziemy powtarzać do momentu otrzymania reszty równej 0.

78:48=1, reszty 30

48:30=1, reszty 18

30:18=1, reszty 12

18:12=1, reszty 6

12:6=2, reszty 0

Otrzymaliśmy resztę równą zero, zatem szukany NWD będzie równy ostatniej niezerowej reszcie:

NWD (282,78) = 6

Opis Algorytmu :

Najprostsza wersja algorytmu rozpoczyna się od wybrania dwóch liczb naturalnych, dla których należy wyznaczyć największy wspólny dzielnik. Następnie z tych dwóch liczb tworzymy nową parę: pierwszą z liczb jest liczba mniejsza, natomiast drugą jest różnica liczby większej i mniejszej. Proces ten jest powtarzany aż obie liczby będą sobie równe – wartość tych liczb to największy wspólny dzielnik wszystkich par liczb wcześniej wyznaczonych. Wadą tej wersji algorytmu jest duża liczba operacji odejmowania, które należy wykonać w przypadku, gdy różnica pomiędzy liczbami z pary jest znacząca.

Operacja odejmowania mniejszej liczby od większej może zostać zastąpiona przez wyznaczanie reszty z dzielenia. W tej wersji nowa para liczb składa się z mniejszej liczby oraz reszty z dzielenia większej przez mniejszą. Algorytm kończy się w momencie, w którym jedna z liczb jest równa zero – druga jest wtedy największym wspólnym dzielnikiem.

Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej.

Pierwsze wzmianki na temat tego algorytmu pojawiły się w dziele Euklidesa zatytułowanym „Elementy”, około trzysetnego roku przed naszą erą, co sprawia, że jest jednym z najstarszych, wciąż używanych algorytmów numerycznych. Pierwsza wersja algorytmu została opisana tylko dla liczb naturalnych. W XIX wieku powstały odmiany algorytmu dla liczb całkowitych Gaussa oraz wielomianów z jedną niewiadomą. Doprowadziło to do powstania współczesnych pojęć algebry abstrakcyjnej, takich jak dziedzina Euklidesa.

Istnieje wiele teoretycznych i praktycznych zastosowań algorytmu. Może on zostać wykorzystany do generowania rytmów muzycznych, stosowanych jako ostinato w muzyce. Jest wykorzystywany w algorytmie RSA. Algorytm Euklidesa używany jest też do rozwiązywania równań diofantycznych, na przykład do znajdowania liczb spełniających zadany układ kongruencji (chińskie twierdzenie o resztach) czy znajdowania liczb odwrotnych w ciele skończonym. Może być także stosowany do generowania ułamków łańcuchowych w metodzie Sturma do obliczania pierwiastków rzeczywistych wielomianu. Wykorzystywany jest również w kilku współczesnych algorytmach do faktoryzacji liczb całkowitych.

Jeżeli algorytm zostanie zaimplementowany poprzez obliczanie reszt z dzielenia, a nie odejmowanie, to jest wydajny dla dużych liczb: nigdy nie wymaga więcej dzieleń niż liczba cyfr (w systemie dziesiętnym) mniejszej liczby pomnożona przez 5. Zostało to udowodnione przez Gabriela Lamé w 1844 i uważane jest za pierwszy przypadek analizy złożoności obliczeniowej algorytmu. Sposoby zwiększenia wydajności algorytmów zostały opracowane w XX wieku.

Największym wspólnym dzielnikiem dwóch liczb jest największa z liczb, która dzieli obie te liczby bez reszty. Algorytm Euklidesa opiera się na założeniu, że największy wspólny dzielnik dwóch liczb nie zmienia się, jeżeli od większej liczby odejmujemy mniejszą.