R78GBM2ZZ46P3
Grafika przedstawia namalowane kredkami cyfry w różnych kolorach oraz różnej wielkości.

I_P_W14_M04 Algorytm Euklidesa

Źródło: Gerald, dostępny w internecie: pixabay.com, domena publiczna.

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

Linia 1. def NWD podkreślnik odejmowanie otwórz nawias okrągły x przecinek y zamknij nawias okrągły dwukropek. Linia 2. while x wykrzyknik znak równości y dwukropek. Linia 3. if x zamknij nawias ostrokątny y dwukropek. Linia 4. x minus znak równości y. Linia 5. else dwukropek. Linia 6. y minus znak równości x. Linia 8. return x.

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

Linia 1. NWD podkreślnik odejmowanie otwórz nawias okrągły 720424 przecinek 4 zamknij nawias okrągły. Linia 2. 4. Linia 3. NWD podkreślnik odejmowanie otwórz nawias okrągły 9203523424 przecinek 23 zamknij nawias okrągły. Linia 4. 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:

Linia 1. import sys. Linia 2. print otwórz nawias okrągły sys kropka maxsize zamknij nawias okrągły. Linia 3. 9223372036854775807. Linia 4. import platform. Linia 5. print otwórz nawias okrągły platform kropka uname otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 6. uname podkreślnik result otwórz nawias okrągły system znak równości apostrof Linux apostrof przecinek node znak równości apostrof zorin minus desktop apostrof przecinek release znak równości apostrof 5 kropka 0 kropka 0 minus 31 minus generic apostrof przecinek. Linia 7. version znak równości apostrof kratka 33 tylda 18 kropka 04 kropka 1 minus Ubuntu SMP Tue Oct 1 10 dwukropek 20 dwukropek 39 UTC 2019 apostrof przecinek. Linia 8. machine znak równości apostrof x86 podkreślnik 64 apostrof przecinek processor znak równości apostrof x86 podkreślnik 64 apostrof zamknij nawias okrągły.

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

9223372036854775807

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

Linia 1. def NWD podkreślnik odejmowanie podkreślnik zliczanie otwórz nawias okrągły x przecinek y zamknij nawias okrągły dwukropek. Linia 2. odejmowania znak równości 0. Linia 3. while x wykrzyknik znak równości y dwukropek. Linia 4. if x zamknij nawias ostrokątny y dwukropek. Linia 5. x minus znak równości y. Linia 6. else dwukropek. Linia 7. y minus znak równości x. Linia 8. odejmowania plus znak równości 1. Linia 10. print otwórz nawias okrągły apostrof NWD apostrof przecinek x przecinek apostrof średnik liczba odejmowań apostrof przecinek odejmowania zamknij nawias okrągły.

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

Linia 1. NWD podkreślnik odejmowanie podkreślnik zliczanie otwórz nawias okrągły 920354 przecinek 22 zamknij nawias okrągły. Linia 2. NWD 2 średnik liczba odejmowań 41839. Linia 3. kratka. Linia 4. NWD podkreślnik odejmowanie podkreślnik zliczanie otwórz nawias okrągły 9203523424 przecinek 22 zamknij nawias okrągły. Linia 5. NWD 2 średnik liczba odejmowań 418341979. Linia 7. NWD podkreślnik odejmowanie podkreślnik zliczanie otwórz nawias okrągły 927566801 przecinek 22 zamknij nawias okrągły. Linia 8. NWD 1 średnik 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.
1
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
Wymyśl pytanie na kartkówkę związane z tematem materiału.

Słownik

modulo
modulo

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

optymalizacja
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

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