Algorytm Euklidesa

rycina

Wiadomo, że nie istnieje ogólny wzór na największy wspólny dzielnik. Jak więc go można wyznaczyć? Metoda, którą poznamy, to jeden z najstarszych spisanych algorytmów zwany algorytmem Euklidesa, od imienia jednego z największych matematyków w całej historii, który go opublikował w swoim wiekopomnym dziele „Elementy”.

Euklides zauważył, że gdy mniejsza z liczb jest równa zero, to największy wspólny dzielnik jest równy drugiej z nich, a gdy obie są dodatnie, to jest równy największemu wspólnemu dzielnikowi ich różnicy oraz mniejszej z nich. ref{MatematykaDyskretna...} Zapisując to zdanie za pomocą wzoru otrzymujemy

\( (a, b) = \begin{cases}a & \textrm{\ jeśli } b = 0 \\ (a-b, b) & \textrm{\ jeśli } b > 0\end{cases} \)

Taki wzór jak powyżej nazywamy rekurencyjnym. Istotą definiowania rekurencyjnego jest odwoływanie się w definicji jakiegoś pojęcia do niego samego, zazwyczaj zastosowanego dla prostszych danych. Tak jak tutaj: żeby zdefiniować największy wspólny dzielnik, wykorzystujemy w definicji też pojęcie największego wspólnego dzielnika, tylko dla nieco mniejszych argumentów. Na dobrą sprawę taka definicja wygląda nieco podejrzanie, ale w rzeczywistości jest całkowicie poprawna. W końcu za jej pomocą jesteśmy w stanie obliczyć największy wspólny dzielnik dla dowolnej pary argumentów. Spróbujmy:

Ćwiczenie

Udowodnij, że zawsze w skończonej liczbie kroków zejdziemy z jednym argumentem do zera.

Zauważmy, że podaliśmy przepis otrzymywania największego wspólnego dzielnika. Jest to właśnie algorytm Euklidesa. Za jego pomocą możemy znaleźć największy wspólny dzielnik dla dowolnej pary argumentów.

Przedstawmy program w notacji, którą formalnie wprowadzimy nieco później, obliczający największy wspólny dzielnik zgodnie z podanym algorytmem.

Euklides 1

<b>Read</b>(a,b);             //Wczytujemy a i b, zakładając że użytkownik wie, że a&gt;=b, a+b&gt;0 
<b>while</b> b &gt; 0 <b>do</b> 
<b>begin</b> 
<b>if</b> a&lt; b <b>then</b> zamień(a,b);  //po wykonaniu tej instrukcji zawsze a&gt;=b 
a:=a-b                //tutaj być może raz wykonamy niepotrzebnie odejmowanie zera 
<b>end</b>; 
<b>Write</b>(a)                //wypisujemy wynik, którym jest wartość a 

Zastanówmy się, jak długo będziemy wykonywali nasz algorytm. Załóżmy, że dane na których pracujemy nie przekraczają \( 10^{30} \). Tak duże liczby jako argumenty nie są jakimś dziwactwem: w rzeczywistości szukanie największego wspólnego dzielnika jest częścią szyfrowania RSA – powszechnie stosowanego protokołu kryptograficznego i zazwyczaj używa się tu znacznie większych liczbach – ponadstucyfrowych.

Dobierzmy możliwie złośliwe dane. Oczywiście aby algorytm działał jak najdłużej, należy odejmować jak najmniejsze wartości w każdym kroku. Weźmy zatem \( a = 10^{30}, b = 1 \). Widać, że dla tych danych wykona się \( 10^{30} \) obrotów pętli: będziemy żmudnie odejmowali jedyneczkę od sporej dość liczby. Jak długo to może potrwać?

Przyjmijmy, że mamy do czynienia z bardzo szybkim komputerem, który na jeden obrót pętli potrzebuje jedną dziesięciomiliardową sekundy \( (10^{-10}s ) \). Zatem w ciągu doby mamy \( 86400\cdot 10^{10} \) obrotów pętli. Dób w ciągu roku jest 365, czyli razem mamy \( 31536 \cdot 10^{13} \) obrotów pętli na rok. A od Wielkiego Wybuchu minęło niespełna 14 miliardów lat, łącznie niespełna \( 5 \cdot 10^{28} \) obrotów pętli. Przyjąwszy, że ktoś włączył nasz komputer na początku Wszechświata i on do dziś z tą zawrotną prędkością wykonuje nasz program dla tych właśnie danych, widzimy, że do dziś wykonałby niespełna jedną dwudziestą wszystkich obliczeń. Jeszcze dwadzieścia parę takich Wszechświatów i program zakończyłby swoje działanie.

Co należy w takiej sytuacji zrobić? Niektórzy myślą, że trzeba kupić szybszy komputer. Żarty na bok. Ale istnieją użytkownicy, którzy gdy im program działa zbyt wolno, myślą przede wszystkim o sprzęcie. W wielu przypadkach jednak główne rezerwy tkwią w samym algorytmie. Dlatego też w trakcie tego kursu będziemy wielką wagę przykładali do jakości algorytmów i szukali jak najlepszych rozwiązań.

Zauważmy (a Euklides to wiedział długo przed nami), że tak naprawdę odejmowanie wykonujemy tylko po to, żeby wyznaczyć resztę z dzielenia \( a \) przez \( b \). W końcu dopóki \( a \) jest większe od \( b \), odejmujemy od \( a \) całkowite wielokrotności \( b \), a zamieniamy rolami \( a \) z \( b \) gdy tylko \( a \) spadnie poniżej \( b \). W momencie, gdy \( a \) z \( b \) zamieniają się rolami, \( a \) ma wartość właśnie reszty z dzielenia \( a \) przez \( b \). Można by zatem pominąć całe to odejmowanie, jeśli udałoby się nam od razu znaleźć tę resztę z dzielenia. A to nie jest takie trudne – można choćby stosować poznane w szkole podstawowej słupkowe dzielenie, które nad kreską daje wynik dzielenia, a na dole – resztę. Zmodyfikujmy zatem algorytm Euklidesa:

Euklides 2

<b>Read</b>(a,b);        //Wczytujemy a i b, zakładając że użytkownik wie, że a&gt;=b, a+b&gt;0 
<b>while</b> b &gt; 0 do 
<b>begin</b> 
 a:=a mod b;
 zamień (a,b) //reszta jest zawsze mniejsza od dzielnika, więc w ciemno możemy zamienić a z b 
<b>end</b>; 
<b>Write</b>(a)          //Wypisujemy wynik 

Podobnie jak poprzednio, możemy bez trudu pokazać, że program się zawsze zakończy.
Jak długo się tym razem będzie wykonywała nasza pętla programu? Jeśli dobranie najbardziej złośliwych danych w poprzednim przypadku było proste, to teraz wcale nie jest oczywiste dla jakich danych spośród liczb 30-cyfrowych program będzie działał najdłużej. Załóżmy, że tak jak wcześniej interesuje nas liczba obrotów pętli. Pomijamy na razie koszt związany z operacją dzielenia z resztą, zakładając że jest on stały.

Ćwiczenie
Znajdź dwie liczby dwucyfrowe, dla których algorytm Euklides 2 wykona się najwięcej razy.