Algorytm Euklidesa

Spis odnośników

Najstarszy algorytm w historii matematyki

#Algorytm Euklidesa jest jednym z najstarszych znanych algorytmów matematycznych. Jego celem jest znalezienie największego wspólnego dzielnika (#NWD) dwóch liczb. Pomimo swojej prostoty, ma on szerokie zastosowanie w teorii liczb, informatyce oraz kryptografii. W tym artykule przyjrzymy się jego historii, zastosowaniom i implementacji w różnych językach programowania.

1. Historia algorytmu Euklidesa

Algorytm został opisany przez Euklidesa około 300 roku p.n.e. w jego monumentalnym dziele „Elementy”, które przez setki lat było podstawą edukacji matematycznej. Choć w tamtych czasach nie istniało pojęcie algorytmów w dzisiejszym rozumieniu, to metoda opisana przez Euklidesa spełnia wszystkie kryteria algorytmu – składa się z dobrze zdefiniowanych kroków i zawsze prowadzi do rozwiązania.

2. Zasada działania algorytmu Euklidesa

Największy wspólny dzielnik (NWD) dwóch liczb to największa liczba, przez którą dzielą się obie liczby bez reszty. Algorytm Euklidesa opiera się na następującej zasadzie:

[math]gcd⁡(a,b) = \gcd(b, a \mod b)[/math]

gdzie [math]\gcd(a, b)[/math] oznacza największy wspólny dzielnik liczb [math]a i a \mod b[/math] to reszta z dzielenia a przez b. Proces powtarzamy, dopóki jedna z liczb nie stanie się zerem.

3. Przykład działania algorytmu

Znajdźmy [math]NWD(252,105)NWD(252, 105)NWD(252,105) [/math]przy użyciu algorytmu Euklidesa:

[math]252 \mod 105 = 42 → Zamieniamy (252,105) na (105,42) [/math]
[math]105 \mod 42 = 21 → Zamieniamy (105,42) na (42,21)[/math]
[math]42 \mod 21 = 0 → Kończymy, ponieważ jedna z liczb to 0.[/math]

Największy wspólny dzielnik to 21.

4. Implementacja algorytmu w różnych językach programowania

4.1. Python

Python umożliwia implementację algorytmu Euklidesa w prosty i czytelny sposób:

1
2
3
4
5
6
7

def nwd(a, b):
while b:
a, b = b, a % b
return a

# Przykład użycia
print(nwd(252, 105)) # Wynik: 21

Powyższy kod wykorzystuje pętlę

while

, by zamieniać wartości liczb do momentu, aż jedna z nich stanie się zerem.

4.2. JavaScript

W JavaScript możemy zapisać algorytm w formie funkcji rekurencyjnej:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

function nwd(a, b) {
return b === 0 ? a : nwd(b, a % b);
}

// Przykład użycia
console.log(nwd(252, 105)); // Wynik: 21

[/lang]



<p>Alternatywnie, można użyć pętli <code>while</code>, podobnie jak w Pythonie.</p>



<h3 class="wp-block-heading"><strong>4.3. Free Pascal</strong></h3>



<p>W Free Pascalu możemy zaimplementować algorytm w sposób klasyczny, wykorzystując funkcję rekurencyjną:</p>



[cc lang="Pascal"]

program Euklides;
uses crt;

function NWD(a, b: Integer): Integer;
begin
if b = 0 then
NWD := a
else
NWD := NWD(b, a mod b);
end;

begin
writeln(NWD(252, 105)); // Wynik: 21
end.

4.4. PHP

W PHP implementacja algorytmu może wyglądać następująco:

1
2
3
4
5
6
7
8
9
10
11
12
13

<?php
function nwd($a, $b) {
while ($b != 0) {
$temp = $b;
$b = $a % $b;
$a = $temp;
}
return $a;
}

// Przykład użycia
echo nwd(252, 105); // Wynik: 21
?>

5. Optymalizacje algorytmu

Chociaż algorytm Euklidesa jest bardzo szybki, można go ulepszyć:

Algorytm Steinera (algorytm binarny NWD) – zamiast dzielenia używa przesunięć bitowych.
Użycie funkcji wbudowanych – w Pythonie możemy użyć
1
math.gcd(a, b)
, w JavaScript
1
BigInt.gcd()
, a w PHP
1
gmp_gcd()
.

6. Zastosowania algorytmu Euklidesa

6.1. Kryptografia

Algorytm RSA – wykorzystuje NWD do znajdowania kluczy publicznych i prywatnych.
Testowanie względnej pierwszości liczb – sprawdzamy, czy gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1, co oznacza, że liczby są względnie pierwsze.

6.2. Informatyka

Algorytmy kompresji danych – stosowany w kodowaniu Huffmana i optymalizacji tablic.
Generowanie liczb losowych – stosowany w algorytmach z zakresu kryptografii.

6.3. Matematyka i teoria liczb

Ułamki niewłaściwe – używany do skracania ułamków.
Rozwiązania równań Diofantycznych – wykorzystywany w rozwiązywaniu równań postaci ax+by=cax + by = cax+by=c.

7. Nierozwiązane problemy i ciekawostki

Czy istnieje szybki algorytm wielomianowy do znajdowania NWD dla ogromnych liczb?
Złożoność algorytmu Euklidesa jest równa O(log⁡b)O(\log b)O(logb) – oznacza to, że działa on niezwykle szybko nawet dla bardzo dużych liczb.

8. Podsumowanie

Algorytm Euklidesa to jedno z najprostszych, ale i najpotężniejszych narzędzi w matematyce. Jego prostota sprawia, że jest wykorzystywany nie tylko w teorii liczb, ale również w nowoczesnej kryptografii i informatyce. Pomimo że pochodzi sprzed ponad 2300 lat, jego znaczenie wciąż rośnie!