Kody źródłowe/Algorytm Euklidesa

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
        a>>=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(< a b)
        a
    (mod (- a b) b))) 

(define (nwd a b)
    (if(=? b 0)
        a
    (nwd b (mod a b))))

SQL

create function NWD(@a int, @b int)
returns int
as
begin
    declare @tmp int
    while @b <> 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[0];
    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 <iostream>
#include <cmath>

int main (){
    int a,b;

    //Pobranie danych
    std::cout << "Podaj a ";
    std::cin >> a;
    std::cout << "\nPodaj b ";
    std::cin >> 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 << "NWD(a,b) = a * p + b * q\n"
        << "NWD(" << a0 << "," << b0 << ") = " 
        << a0 << " * " << p << " + " 
        <<  b0 << " * " << q << '\n';
}

#include <iostream>

int v,w;

template <class _t1, class _t2, class _t3>
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 <class _u1, class _u2, class _u3>
    tripl(const tripl<_u1,_u2,_u3>& _t)
        : d(_t.d), x(_t.x), y(_t.y) { };
};

template <class typ>
tripl<typ,typ,typ> egcd(typ _a, typ _b) {
    // szablon funkcji obliczającej NWD
    if(_b==0) 
        return tripl<typ,typ,typ>(_a,1,0);
    tripl<typ,typ,typ> tmp;
    tmp = egcd<typ>(_b,_a%_b);
    return tripl<typ,typ,typ> (tmp.d, tmp.y, tmp.x-((int)(_a/_b))*tmp.y);
}

int main() {
    std::cout << "Podaj pare liczb rozdzielonych spacja\n";
    std::cin >> v >> w;
    tripl<int,int,int> ret;
    ret = egcd(v,w);
    std::cout << "gcd(" << v << ", " << w << ") = " << ret.d << " = " 
        << ret.x << "*" << v << (ret.y>0? " + " : " - ") 
        << (ret.y>0? ret.y : -ret.y) << "*" << w << '\n';
    return 0;
}