Przejdź do zawartości

Kody źródłowe/Algorytm Euklidesa

Z Wikibooks, biblioteki wolnych podręczników.
Algorytm Euklidesa • Kod źródłowy
Algorytm Euklidesa
Kod źródłowy
Implementacje algorytmu Euklidesa.
Wikipedia
Zobacz w Wikipedii hasło 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

[edytuj]
 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'
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
function nwd(a, b) {
    while (a != b) {
        if (a>b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}
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;
}
	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

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;
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);
};
function NWD($a, $b) {
    while ($b) {
        $tmp = $a%$b;
        $a = $b;
        $b = $tmp;
    }
    return $a;
}


function nwd(a, b) {
    var r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
    nwd(X,0,X).
    nwd(X,Y,Wynik):- not(Y==0),
        X1 is X mod Y,
        nwd(Y,X1,Wynik1),
        Wynik is Wynik1.
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
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

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))))
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

[edytuj]
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

[edytuj]
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
#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;
}