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

Vstupnými parametrami funkcie sú dve kladné celé čísla m a n, výstupom funkcie je trojica čísel (d, a, b) spĺňajúca rovnosť d = a·m + b·n, kde d je najväčší spoločný deliteľ čísel m a n.

Poznámka: Dobrý kompilátor/interpreter by mal príkaz while (1) (funkcia rea_1()) zrealizovať ako návestie skoku nekonečného cyklu a nie ako ďalšiu podmienku. V opačnom prípade je vhodnejšie použiť cyklus do-while/repeat-until (funkcia rea_2()).

Perl

sub rea_1 {
	my ($c, $d) = @_;
	my ($a_old, $b_old, $a, $b) = (1, 0, 0, 1);
	my ($p, $z);

	while (1) {
		($p, $z) = ( int $c/$d, $c%$d);
		return ($d, $a, $b) unless ($z);

		($a, $a_old) = ($a_old - $a*$p, $a);
		($b, $b_old) = ($b_old - $b*$p, $b);
		($c, $d) = ($d, $z);
	}
}

sub test {
	my ($m, $n) = (196, 34);
	($m, $n) = ($n, $m) if $m < $n; # ak m<n, prva interacia Euklidovho algoritmu iba vymiena ich hodnoty
	@vysledok = rea_1($m, $n);

	$" = ", ";
	print "(d, a, b) = (@vysledok)\n";
	printf ("%d = %d.%d%+d.%d\n", $vysledok[0], $vysledok[1], $m, $vysledok[2], $n);
}

cyklus do-while:

sub rea_2 {
	my($c, $d) = @_;
	my ($a_old, $b_old, $a, $b) = (1, 0, 0, 1);
	my ($p, $z) = ( int $c/$d, $c%$d);
	return ($d, $a, $b) unless ($z);

	do {
		($a, $a_old) = ($a_old - $a*$p, $a);
		($b, $b_old) = ($b_old - $b*$p, $b);
		($c, $d) = ($d, $z);

		($p, $z) = ( int $c/$d, $c%$d);
	} while ($z);
	return ($d, $a, $b);
}

Python

def rea_1(c, d):
	a_old, b_old, a, b = 1, 0, 0, 1
	while True:
		p, z = c//d, c%d
		if z == 0:
			return d, a, b

		a, a_old = a_old - a*p, a
		b, b_old = b_old - b*p, b
		c, d = d, z

def test():
	m, n = 196, 34
	if m<n: m, n = n, m
	vysledok = rea_1(m, n)

	print "(d, a, b) = " + str(vysledok)
	print ("%d = %d.%d%+d.%d\n" % (vysledok[0], vysledok[1], m, vysledok[2], n))

Python cyklus do-while nepozná:

def rea_2(c, d):
	a_old, b_old, a, b = 1, 0, 0, 1

	p, z = c//d, c%d
	while (z != 0):
		a, a_old = a_old - a*p, a
		b, b_old = b_old - b*p, b
		c, d = d, z
		p, z = c//d, c%d

	return d, a, b

Pozri aj

• Implementácia algoritmov/Euklidov algoritmus