Algorytm Euklidesa - znajdowanie największego wspólnego dzielnika

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 19982 razy

Algorytm Euklidesa stanowi wstęp do utworzenia jego rozszerzonej wersji ważnej przy szyfrowaniu danych szyfrem RSA z kluczem prywatnym i publicznym. Podstawowy model tego algorytmu operuje na różnicach dwóch liczb całkowitych a i b tak długo, aż te liczby osiągną taką samą wartość. Ważne jest aby odejmować od największej mniejszą liczbę.

O wiele lepszym i efektywniejszym rozwiązaniem jest użycie algorytmu wykorzystującego reszty z dzielenia liczb a i b. Po każdym kroku liczba a przyjmuje wartość dzielnika, czyli liczby b, która w kolejnych krokach przyjmuje wartość a % b (czyli reszty z dzielenia a przez b). Oto przykładowy kod napisany w Pythonie pokazujący obie te metody wyznaczania największego wspólnego dzielnika dwóch liczb a i b:

#!/usr/bin/env python def NWD(a, b): c = 0 while b != 0: c = a % b print("a = {a}; b = {b}".format(a = a, b = b)) a, b = b, c print("a = {a}; b = {b}".format(a = a, b = b)) return a def classicNWD(a, b): while a != b: a, b = max(a, b), min(a, b) print("a = {a}; b = {b}".format(a = a, b = b)) a = a - b print("a = {a}; b = {b}".format(a = a, b = b)) return a def main(args): a = int(input("Podaj pierwszą liczbę całkowitą dodatnią: ")) b = int(input("Podaj drugą liczbę całkowitą dodatnią: ")) print("Metoda z wydajniejsza: n") print("nNajwiększy wspólny dzielnik liczb {a} i {b} jest równy: {NWD}".format(a = a, b = b, NWD = NWD(a, b))) print("nObliczanie NWD metodą klasyczną:n") print("nNajwiększy wspólny dzielnik liczb {a} i {b} jest równy: {NWD}".format(a = a, b = b, NWD = classicNWD(a, b))) return 0 if __name__ == '__main__': import sys sys.exit(main(sys.argv))

Przykład działania powyższego programu dla liczb a = 121 i b = 21:

Podaj pierwszą liczbę całkowitą dodatnią: 121
Podaj drugą liczbę całkowitą dodatnią: 21
Metoda z wydajniejsza:

a = 121; b = 21
a = 21; b = 16
a = 16; b = 5
a = 5; b = 1
a = 1; b = 0

Największy wspólny dzielnik liczb 121 i 21 jest równy: 1

Obliczanie NWD metodą klasyczną:

a = 121; b = 21
a = 100; b = 21
a = 79; b = 21
a = 58; b = 21
a = 37; b = 21
a = 21; b = 16
a = 16; b = 5
a = 11; b = 5
a = 6; b = 5
a = 5; b = 1
a = 4; b = 1
a = 3; b = 1
a = 2; b = 1
a = 1; b = 1

Największy wspólny dzielnik liczb 121 i 21 jest równy: 1
Aby kontynuować, naciśnij dowolny klawisz . . .

Jak widać liczba operacji koniecznych do wyznaczenia wspólnego dzielnika liczb a i b w przypadku klasycznego algorytmu Euklidesa wymaga wykonania znacznie większej liczby operacji niż w przypadku algorytmu wykorzystującego resztę z dzielenia.

Propozycje książek