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
[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;
}