Euklides pierwotnie sformułował ten problem geometrycznie, jako szukanie wspólnej "miary" dwóch odcinków. Jego algorytm polegał na kolejnym odejmowaniu krótszego odcinka od dłuższego.
Implementacja algorytmu Euklidesa
Asembler ARM loop CMP Ri, Rj ; porównaj i z j, ustawiając flagi warunkowe: ; - "GT" dla (i > j) ; - "LT" dla (i < j) ; - "NE" dla (i != j) SUBGT Ri, Ri, Rj ; jeśli "GT" (większa niż ang. greater than), wykonaj i := i - j; SUBLT Rj, Rj, Ri ; jeśli "LT" (mniejsza niż ang. less than), wykonaj j := j - i; BNE loop ; jeśli "NE" (nie równy ang.not equal), wykonaj skok do etykiety 'loop'
NASM x86 section .text global getgcd getgcd: push ebp mov ebp,esp mov eax,[ebp+8] mov ebx,[ebp+12] petla: cmp eax,ebx jg wiekszy jl mniejszy jmp koniec wiekszy: sub eax,ebx jmp petla mniejszy: sub ebx,eax jmp petla koniec: mov esp,ebp pop ebp ret
ActionScript function nwd(a, b) { while (a != b) { if (a>b) { a -= b; } else { b -= a;
return a; }
C/C++, C#, Java int gcd(int a,int b){ return b?gcd(b,a%b):a; } int nwd(int a, int b) { if (b == 0) return a; return nwd(b, (a % b)); } int nwd(int a, int b){ int tmp; while(b != 0){ tmp = a % b; a = b; b = tmp;
return a; }
albo za pomocą odejmowania:
while (i != j) { if (i > j) i -= j; else j -= i; }
MARIE
Input / AC = wejscie Store X / X = AC Input / AC = wejscie Store Y / Y = AC While, Load X / AC = X Subt Y / AC -= Y Skipcond 400 / If (AC==0) [X!=Y] to pomin nast. rozkaz Jump If / If (X!=Y) skocz do If Jump Return / If (X==Y) to wyjdz z petli If, Skipcond 800 / If (AC>0) [X>Y] to pomin nast. rozkaz Jump Else / If (X<Y) to skocz do Else Load X / AC = X Subt Y / AC -= Y Store X / X = AC Jump While / skocz do While (petla) Else, Load Y / AC = Y Subt X / AC -= X Store Y / Y = AC Jump While / skocz do While (petla) Return, Load X / AC = X Output / daj AC na wyjscie Halt / koniec X, dec 0 Y, dec 0
Pascal
Można to zilustrować następującą implementacją w Pascalu.
function nwd(a,b: Integer): Integer; begin while a <> b do if a > b then a := a-b else b := b-a; nwd := a; end;
albo nieco inaczej:
function nwd(a, b: Integer): Integer; var tmp: Integer; begin repeat tmp := a mod b; a := b; b := tmp; until b = 0; nwd := a; end;
Perl
sub nwd { my ($a,$b)=@_; # drugi argument nie powinien być większy od pierwszego ($b,$a)=($a,$b) if $b>$a; return $a if $b==0; nwd($b,$a%$b);
PHP
function NWD($a, $b) { while ($b) { $tmp = $a%$b; $a = $b; $b = $tmp;
return $a; }
Javascript
function nwd(a, b) { var r; while (b) { r = a % b; a = b; b = r;
return a; }
Prolog nwd(X,0,X). nwd(X,Y,Wynik):- not(Y==0), X1 is X mod Y, nwd(Y,X1,Wynik1), Wynik is Wynik1.
Python
def nwd(a, b): while b: a, b = b, a%b return a
Wersja uproszczona.
def nwd(a, b): while b: c = b b = a%b a = c return a
Wersja z odejmowaniem "odcinków" w Pythonie.
def nwd(a,b): while a != b: if a > b: a -= b else: b -= a return a
Ruby
def bgcd(a,b) g=1 while(a&1==0 && b&1==0) g>=1 b>>=1 end while b!=0 if a&1 == 0 a>>=1 elsif b&1 == 0 b>>=1 else if (a>b) a-=b a>>=1 else b-=a b>>=1 end end end return g*a end
def nwd(a,b) if a > b then a -= b else b -= a end while a != b; return a end dla wielu liczb gdzie arr - tablica liczb def nwd(arr) a = arr.pop arr.each do |b| if a > b then a -= b else b -= a end while a != b; end return a end Funkcja biblioteki standardowej: a.gcd b
Scheme
Definicja funkcji wynika bezpośrednio ze wzoru rekurencyjnego:
(define (nwd a b) (if (= b 0) a (nwd b (modulo a b))))
(define (mod a b) (if( 0 select @tmp = @a%@b, @a = @b, @b = @tmp return @a end
Dla większej ilości liczb
PHP function gcdp($a, $b) { // funkcja pomocnicza if ($b == 0) { return $a; } else { return gcdp($b, $a % $b);
function gcd($list) { // główna funkcja sort($list); $g = $list; for ($i = 0; $i < count($list)-1; $i++) { $g = gcdp($g, $list[$i]);
return $g; }
Rozszerzony algorytm Euklidesa
SQL
create function nwd(@a int, @b int) returns @m table(p int, q int) /* Funkcja zwraca rozwiązanie równania: a*p + b*q = NWD(a,b) */ as begin declare @r int, @q int, @x int, @x1 int, @x2 int, @y int, @y1 int, @y2 int
select @q = @a/@b, @r = @a - @q*@b, @x2 = 1, @x1 = 0, @x = 1, @y2 = 0, @y1 = 1, @y = 1 - @q
while @r <> 0 select @a = @b, @b = @r, @x = @x2 - @q*@x1, @x2 = @x1, @x1 = @x, @y = @y2 - @q*@y1, @y2 = @y1, @y1 = @y, @q = @a/@b, @r = @a - @q*@b
insert into @m select @x, @y
return end
C++
#include #include
int main (){ int a,b;
//Pobranie danych std::cout > a; std::cout > b; if ( (a < 0) || (b < 0) ){ std::cout << "Wartosci a i b powinny byc wieksze od zera\n"; exit (1);
//zachowanie pierwotnych wartosci int a0 = a, b0 = b;
//Zapewnia spelnienie niezmiennika p*a0 + q*b0 = a oraz r*a0 + s*b0 = b int p = 1, q = 0, r = 0, s = 1; int c, quot, new_r, new_s;
//algorytm while (b != 0){ c = a % b; quot = lrint (floor (a/b)); a = b; b = c; new_r = p - quot * r; new_s = q - quot * s; p = r; q = s; r = new_r; s = new_s;
std::cout
int v,w;
template struct tripl { // wzorowane na kontenerze pair z biblioteki STL _t1 d; _t2 x; _t3 y; tripl() : d(), x(), y() { }; tripl(const _t1& _a, const _t2& _b, const _t3& _c) : d(_a), x(_b), y(_c) { }; template tripl(const tripl& _t) : d(_t.d), x(_t.x), y(_t.y) { };
template tripl egcd(typ _a, typ _b) { // szablon funkcji obliczającej NWD if(_b==0) return tripl(_a,1,0); tripl tmp; tmp = egcd(_b,_a%_b); return tripl (tmp.d, tmp.y, tmp.x-((int)(_a/_b))*tmp.y); }
int main() { std::cout > v >> w; tripl ret; ret = egcd(v,w); std::cout 0? " + " : " - ") 0? ret.y : -ret.y) << "*" << w << '\n'; return 0; }