Przeczytaj

Przeanalizujmy działanie algorytmu Euklidesa w wersji z odejmowaniem. Oto jego realizacja w języku Python:

def NWD_odejmowanie(x, y):
	while x != y:
		if x > y:
			x -= y
		else:
			y -= x

	return x

Wyznaczmy przykładowe NWD, używając powyżej zdefiniowanej funkcji:

NWD_odejmowanie(720424,4)
4
NWD_odejmowanie(9203523424,23)
1

Spróbujmy wykorzystać tę metodę w przypadku dużych liczb. W języku Python istnieje ograniczenie maksymalnej wartości typu int. Możemy to sprawdzić, wywołując odpowiednie właściwości modułów sys oraz platform:

import sys
print(sys.maxsize)
9223372036854775807
import platform
print(platform.uname())
uname_result(system='Linux', node='zorin-desktop', release='5.0.0-31-generic',
version='#33~18.04.1-Ubuntu SMP Tue Oct 1 10:20:39 UTC 2019', 
machine='x86_64', processor='x86_64')

Zatem największą liczbą całkowitą, którą możemy podać w 64‑bitowym systemie Linux, jest:

9 223 372 036 854 775 807

Oto wersja programu, która liczy, ile operacji odejmowania należy wykonać podczas wyznaczania NWD:

def NWD_odejmowanie_zliczanie(x, y):
    odejmowania = 0
	while x != y:
		if x > y:
			x -= y
		else:
			y -= x
        odejmowania += 1

	print('NWD',x,'; liczba odejmowań', odejmowania)

Wyznaczmy NWD dla liczb o wiele mniejszych niż maksymalna wartość int zapisana w 64‑bitowym systemie Linux:

NWD_odejmowanie_zliczanie(920354,22)
NWD 2 ; liczba odejmowań 41839
#
NWD_odejmowanie_zliczanie(9203523424,22)
NWD 2 ; liczba odejmowań 418341979

NWD_odejmowanie_zliczanie(927566801,22)
NWD 1 ; liczba odejmowań 42162136

Niewykluczone, że obliczenia zajmą ponad minutę. W przypadku bardzo dużych liczb program uruchomiony na szybkim komputerze mógłby pracować nawet kilkadziesiąt minut (ze względu na dużą liczbę operacji odejmowania). Przedstawiamy obraz z Monitora systemu – pokazuje on, że nawet proste obliczenia potrafią obciążać procesor:

RC1z2TvxYr5sZ1

Zdjęcie ekranu przedstawia 3 wykresy. Pierwszy to zestawienie obciążenia 8 rdzeni procesora. Drugi to wykorzystanie pamięci i przestrzeni wymiany. Ostatni to wykres pobierania i wysyłania danych w sieci. Wykorzystanie internetu jest umiarkowane, wartości skaczą, ale nie przekraczajć 50%. Wykorzystanie pamięci jest stałe, na około 40%. Wykorzystanie procesora nie jest równomierne, jeden z rdzeni wykorzystany jest na 100%, podczas gdy inne nie przekraczają 20%. — Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Polecenie 1

Możemy zmierzyć czas niezbędny do obliczenia NWD. Spróbujmy napisać funkcję NWD_odejmowanie_zliczanie_czas(x, y), która oprócz liczby odejmowań poda czas niezbędny do ich wykonania.

Specyfikacja problemu:

Dane:

x, y – liczby całkowite

Wynik:

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

R6QnFro3RAMwl

Na szczęście proces wyznaczania NWD da się zoptymalizowaćoptymalizacjazoptymalizować. 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 2

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

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)

Problem 1

Algorytm Euklidesa wykorzystujący odejmowanie opiera swoje działanie o spostrzeżenie, że największy wspólny dzielnik jest równy największemu wspólnemu dzielnikowi mniejszej liczby i różnicy liczb większej oraz mniejszej.

Napisz program, który obliczy największy wspólny dzielnik dwóch liczb całkowitych dodatnich. Zaimplementuj algorytm Euklidesa, wykorzystując:

odejmowanie,
resztę z dzielenia.

Specyfikacja problemu:

Dane:

a, b – liczby całkowite

Wynik:

NWD – liczba całkowita, największy wspólny dzielnik liczby a i b

R1GE0flVxkqol

Polecenie 3

Porównaj swoje rozwiązanie z przedstawionym w filmie.

RbNtfLMrgEPh1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Słownik

modulo

operacja wyznaczania reszty z dzielenia dwóch liczb; działanie takie oznaczane jest w Pythonie operatorem %

optymalizacja

upraszczanie procesu, poszukiwanie najlepszego rozwiązania z punktu widzenia pewnego kryterium, np. liczby wykonywanych operacji przez procesor czy czasu niezbędnego do przeprowadzonych działań lub ilości zajmowanej pamięci

Wprowadzenie

Audiobook

Słownik