Implementacja zoptymalizowanej wersji algorytmu Euklidesa - I_P_W14_M04 Algorytm Euklidesa

R78GBM2ZZ46P3

Na szczęście proces wyznaczania NWD da się zoptymalizować. Przeanalizujmy zmodyfikowaną wersję algorytmu, tzw. obliczanie NWD metodą dzielenia z resztą.

Oto implementacja algorytmu w języku Python:

def NWD_modulo(x, y):
	while y > 0:
		modulo = x%y
		x = y
		y = modulo
	return x

Wersja programu, która zlicza wykonane operacje, może wyglądać następująco:

def NWD_modulo_zliczanie(x, y):
    dzielenia = 0
	while y > 0:
		modulo = x % y
		x = y
		y = modulo
        dzielenia += 1

	print('NWD',x,'; liczba dzieleń', dzielenia)

Wyznaczmy NWD dla dużych argumentów funkcji. Okaże się, że liczba wykonywanych operacji jest bardzo mała:

NWD_modulo_zliczanie(927566801,22)
NWD 1 ; liczba dzieleń 3

Polecenie 1

Możemy obliczyć czas niezbędny do wyznaczenia NWD. Zdefiniujmy funkcję NWD_modulo_zliczanie_czas(x, y), która oprócz liczby operacji zmierzy także czas ich wykonania.

Specyfikacja problemu:

Dane:

x, y – liczby całkowite

Wynik:

NWD – liczba całkowita, największy wspólny dzielnik liczb x i y
dzielenia – liczba całkowita, liczba wykonanych operacji
t – czas trwania programu; liczba rzeczywista

RNwx1csJkIKTW

def NWD_modulo_zliczanie_czas(x, y):
    from time import time
    t0 = time()
    dzielenia = 0
    while y > 0:
        modulo = x % y
        x = y
        y = modulo
        dzielenia += 1

    print('NWD',x,'; liczba dzieleń', dzielenia, 'czas =',time()-t0)

# wynik działania

NWD_modulo_zliczanie_czas(927566801,22)
# NWD 1 ; liczba dzieleń 3 czas = 1.430511474609375e-06

# nawet dla bardzo dużej liczby działa błyskawicznie
NWD_modulo_zliczanie_czas(922337203685477584,22)
# NWD 2 ; liczba dzieleń 3 czas = 1.6689300537109375e-06

Plik z programem do pobrania:

R1PK7VRNNE2Q8

Przycisk do pobrania pliku TXT z programem.

Plik TXT o rozmiarze 566.00 B w języku polskim

Dla zainteresowanych

Możemy obliczyć NWD dla więcej niż dwóch liczb.

Obliczenie NWD dla trzech liczb odbywa się w dwóch etapach. Najpierw wyznaczamy NWD dla liczb pierwszej i drugiej oraz NWD liczb drugiej i trzeciej. Następnie obliczamy NWD dla otrzymanych wyników. Przedstawmy tę zasadę za pomocą pseudokodu:

obliczenie NWD(a, b, c):

  do zmiennej tymczasowej x przypisz NWD(a,b)
  do zmiennej tymczasowej y przypisz NWD(b,c)

  wynikiem będzie NWD(x,y)

# inny sposób rozwiązania problemu:
NWD(a,b,c)=NWD(NWD(a,b),c)

Wersja zoptymalizowana (wykorzystująca operacje dzielenia i obliczania reszty z dzielenia)

Misja: Ćwicz i zwyciężaj