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
edytujfunction 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
edytujcreate 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;
}