Algorytm Euklidesa

Algorytm Euklidesa jest opisem czynności, które należy wykonać, aby znaleźć największy wspólny dzielnik dwóch liczb całkowitych (czyli największą liczbę naturalną, która dzieli obie liczby bez reszty). Aby zrozumieć sam algorytm, musimy zwrócić uwagę na pewną właściwość dwóch dowolnych liczb całkowitych.

Jeżeli weźmiemy parę liczb (przykładowo, 18 oraz 12) i od większej z nich odejmiemy mniejszą, to wynik działania wraz z mniejszą liczbą utworzy nową parę. Jej największy wspólny dzielnik będzie taki sam, jak w przypadku oryginalnej pary. Sprawdźmy to na liczbach 18 i 12. Ich największym wspólnym dzielnikiem jest 6.

Teraz od liczby 18 odejmiemy 12:

Wynik działania wraz z mniejszą liczbą tworzą nową parę: 12 i 6. Największy wspólny dzielnik się nie zmienił – wciąż wynosi on 6.

Ta właściwość jest fundamentem algorytmu Euklidesa. Opisana cecha jest wspólna dla każdej pary liczb, a zatem możemy powtórzyć proces odejmowania i tworzenia nowej pary dla wartości 12 oraz 6:

Wynik oraz mniejsza liczba z pary początkowej składają się na kolejną parę: 6 i 6. Największym wspólnym dzielnikiem identycznych liczb jest każda z nich.

Okazuje się, że biorąc dwie dowolne liczby i wiele razy wykonując opisane wyżej czynności (odejmowanie i tworzenie kolejnych par), otrzymamy w końcu dwie identyczne liczby. Każda kolejna para ma taki sam największy wspólny dzielnik. Zatem ostatnie elementy ciągu są największym wspólnym dzielnikiem pierwszej pary.

To właśnie jest algorytm Euklidesa. Aby przełożyć go na język programowania, najlepiej jest posłużyć się schematem blokowym:

Najpierw tworzymy zmienne a oraz b. Jest to para liczb, dla której musimy znaleźć największy wspólny dzielnik. Bloki pogrubione są elementami pętli while. Sprawdzamy warunek naszej pętli (czy wartości zmiennych a i b nie są równe – jeśli są równe, wówczas od razu otrzymujemy największy wspólny dzielnik). Zmienna a ma jednak wartość 36, a zmienna b wynosi 8, więc wyrażenie logiczne ma wartość logiczną prawda.

Kolejnym krokiem jest sprawdzenie, która z liczb jest większa, ponieważ od niej musimy odjąć mniejszą. W tym przypadku będzie to zmienna a. Podążamy więc do bloku wskazanego przez strzałkę z napisem prawda i od a odejmujemy b. Wynikiem zastępujemy poprzednią wartość zmiennej a. Nowa para składa się z różnicy z odejmowania oraz mniejszej liczby z poprzedniej pary.

Wracamy na początek pętli while, ponownie sprawdzamy warunek i postępujemy tak do chwili, gdy wartości zmiennych a oraz b będą takie same. Program wyświetla wówczas wartość zmiennej a – jest to właśnie największy wspólny dzielnik.

Analiza efektywności algorytmu

Program działa i wydaje się, że nie ma kłopotów ze znalezieniem NWDNWDNWD dowolnej pary liczb całkowitych. Czy jest tak na pewno? Pierwsze problemy pojawią się, gdy zaczniemy szukać największego wspólnego dzielnika dużych liczb. A jeżeli jedna z liczb w parze jest bardzo duża, a druga bardzo mała, będzie jeszcze gorzej. Program odejmuje od siebie liczby aż do momentu, kiedy staną się one równe. Przy dużej dysproporcji wartości potrzebnych jest wiele przejść pętli. Zajmuje to czas i zasoby komputera.

Załóżmy, że szukamy NWD liczb a = 1 000 000 oraz b = 50 000. Prześledźmy wykonywane operacje:

...

W tym przypadku pętla while wykonała 19 iteracji. Nie jest to zły wynik. Zobaczmy jednak, co się stanie jeżeli spróbujemy znaleźć największy wspólny dzielnik pary 1 000 000 oraz 2.

...

Tym razem pętla while była wykonywana aż 499 999 razy.

Na szczęście istnieje inna wersja algorytmu Euklidesa. Wykorzystywany jest w niej operator modulooperator modulooperator modulo. Prezentacja na kolejnej stronie objaśnia ten właśnie wariant algorytmu.

Słownik