Euklides

Wstęp

Algorytm Euklidesa pozwala wyznaczyć największy wspólny dzielnik dwóch liczb za pomocą logarytmicznej (względem ich wartości) liczby operacji arytmetycznych (porównań, odejmowania i operacji modulo lub przesunięcia bitowego). Jego rozszerzona wersja pozwala na wyrażenie NWD jako kombinacji liniowej argumentów.

Wymagania

(wpisy w tej sekcji odpowiadające tematom opisanym na wikidot powinny być odnośnikami do odpowiednich stron)

Matematyka:

• kongruencje modulo, pojęcie NWD

Programowanie:

• rekurencja

Wersja naiwna O(n)

Oparta o równości:

(1)

\begin{align} nwd(a, 0) = a \\ nwd(a, b) = nwd(b, a) \\ nwd(a, b) = nwd(a, a-b) \end{align}

Drugą równość stosujemy dla a<b.
W każdym kroku prawa liczba maleje (ale być może tylko o 1), skąd liniowa złożoność.

Wersja O(log(n)) z dzieleniem

Oparta o równości:

(2)

\begin{align} nwd(a, 0) = a \\ nwd(a, b) = nwd(b, a\mod b) \end{align}

W każdym kroku prawa liczba maleje przynajmniej dwukrotnie, skąd logarytmiczna złożoność.

Wersja O(log(n)) z przesunięciem bitowym

Oparta o równości:

(3)

\begin{align} nwd(a, 0) = a \\ nwd(2a, 2b) = 2 nwd(a,b) \\ nwd(2a, 2b+1) = nwd(a, 2b+1) \\ nwd(2a+1, 2b) = nwd(2a+1, b) \\ nwd(2a+1, 2b+1) = nwd(2b+1, 2(a-b)) = nwd(2b+1, a-b) \end{align}

W każdym kroku któraś z liczb maleje dwukrotnie, skąd logarytmiczna złożoność.

Implementacja i testowanie

Zadanie to jest niezłym podstawowym ćwiczeniem na programowanie z użyciem rekurencji i zamianę wersji rekurencyjnej na iteracyjną.
Jeśli dopuszczamy na wejściu liczby ujemne, to warto zauważyć, że operacja modulo może zachowywać się niezgodnie z intuicją i to w sposób zależny od języka programowania lub nawet (przynajmniej formalnie) od architektury procesora czy wersji kompilatora!!! Najbezpieczniej obsłużyć ujemne argumenty samemu, biorąc od samego początku wartość bezwzględną.

W testach warto uwzględnić:

• wszystkie kombinacje z zerem (dość częsty błąd to niepoprawna obsługa zera jako pierwszego argumentu)
• kombinacje bardzo dużych liczb z bardzo małymi (dające pesymistyczną złożoność "naiwnej" wersji)
• kolejne liczby Fibonacciego (dające pesymistyczną złożoność wersji z modulo)
• liczby postaci (4^k-1)/3, (2*4^k+1)/3 (dające pesymistyczną złożoność wersji z przesunięciem bitowym)
• obsługę liczb ujemnych (najlepiej wszystkie 9 kombinacji +/0/-)

Proponowane ćwiczenia na zajęcia

Poszukiwanie opisanych powyżej przypadków testowych dających pesymistyczne czasy działania jest dobrym ćwiczeniem dla lepszych uczniów (łatwiejszym, jeśli wcześniej były omawiane liczby Fibonacciego).

Porównanie szybkości działania obydwu szybkich metod: można tu zwrócić uwagę na fakt, że dla różnych danych jeden bądź drugi wykonywać będą więcej iteracji, ma zatem sens porównać albo czasy przy tej samej liczbie iteracji (na spreparowanych odpowiednio danych), albo czasy na przypadkach pesymistycznych.

Istniejące zadania

(w tej sekcji zamieszczać będziemy krótko opisane odnośniki do opartych na danym algorytmie zadań na publicznych serwisach online judge lub - w wypadku zadań wymagających dłuższego komentarza - odpowiadających im podstronom wikidot)

Wykorzystywany w:

(w tej sekcji zamieszczać będziemy linki do podstron opisujących algorytmy wykorzystujące ten jako istotny fragment)