Implementácia algoritmov/Euklidov algoritmus

Euklidov algoritmus EA1. Nech m a n sú kladné celé čísla. Algoritmus nájde ich najväčší spoločný deliteľ d = NSD(m,n).

1. [Inicializácia premenných.] Priraďte c ← m, d ← n. (Obsah premenných m a n zostane zachovaný.)
2. [Výpočet zvyšku po delení.] Vypočítajte zvyšok z po delení c / d. (Platí 0 ≤ z < d.)
3. [Ukončovacia podmienka.] Ak z = 0 tak koniec, pričom NSD(m,n) = d.
4. [Ďalšia iterácia.] Priraďte c ← d, d ← z a vráťte sa do bodu 2.

Poznámka: Ak m < n, tak prvá iterácia iba vymení obsah premenných c a d, čo sa dá efektívnejšie dosiahnuť úpravou kroku 1:

Euklidov algoritmus EA2. Nech m a n sú kladné celé čísla. Algoritmus nájde ich najväčší spoločný deliteľ d = NSD(m,n).

1. [Inicializácia premenných.] Ak m ≥ n tak priraďte c ← m, d ← n, inak priraďte c ← n, d ← m. (Obsah premenných m a n zostane zachovaný.)
2. [Výpočet zvyšku po delení.] Vypočítajte zvyšok z po delení c / d. (Platí 0 ≤ z < d.)
3. [Ukončovacia podmienka.] Ak z = 0 tak koniec, pričom NSD(m,n) = d.
4. [Ďalšia iterácia.] Priraďte c ← d, d ← z a vráťte sa do bodu 2.

Poznámka: Krok 4 iba zamieňa obsah premenných, čomu sa dá vyhnúť:

Euklidov algoritmus EA3. Nech m a n sú kladné celé čísla. Algoritmus nájde ich najväčší spoločný deliteľ d = NSD(m,n).

1. [Inicializácia premenných.] Ak m ≥ n tak priraďte c ← m, d ← n, inak priraďte c ← n, d ← m. (Obsah premenných m a n zostane zachovaný.)
2. [Výpočet zvyšku po delení.] Vypočítajte zvyšok po delení c / d a výsledok uložte do premennej c (0 ≤ c < d).
3. [Ukončovacia podmienka.] Ak c = 0 tak koniec, pričom NSD(m,n) = d.
4. [Výpočet zvyšku po delení.] Vypočítajte zvyšok po delení d / c a výsledok uložte do premennej d (0 ≤ d < c).
5. [Ukončovacia podmienka.] Ak d = 0 tak koniec, pričom NSD(m,n) = c, inak sa vráťte do bodu 2.

Perl

EA2:

sub ea_2 {
	my($c, $d);
# 1:
	if (@_[0] >= @_[1]) {
		($c, $d) = @_;
	} else {
		($d, $c) = @_;
	}
# 2:
	my $z = $c%$d;
# 3:
	return $d unless ($z);

	do {
# 4:
		($c, $d) = ($d, $z);
# 2:
		$z = $c%$d;
# 3:
	} while ($z);
	return $d;
}

sub test {
	($m, $n) = (34,196);
	@vysledok = ea_2($m, $n);
	print "NSD($m,$n) = @vysledok\n";
}

EA3:

sub ea_3 {
	my($c, $d);
# 1:
	if (@_[0] >= @_[1]) {
		($c, $d) = @_;
	} else {
		($d, $c) = @_;
	}

	do {
# 2:
		$c = $c%$d;
# 3:
		return $d unless ($c);
# 4:
		$d = $d%$c;
# 5:
	} while ($d);
	return $c;
}

Pozri aj

• Implementácia algoritmov/Rozšírený Euklidov algoritmus