[GAP Forum] Extended Euclid Algorithm Need HELP
sam johnson
liveat1892 at gmail.com
Tue Nov 19 18:39:57 GMT 2013
Hey guys ... I'm writing two algorithms for the extended euclidean
algorithm ( iterative & recursive). The iterative version works just fine
except that it gives false results for negative input. How can I modify?
code:
extEuclid := function(a,b)
local x, y, u, v,m,n,r,q;
x:=0;
y:=1;
u:=1;
v:=0;
while a>0 or a<0 do
q := QuoInt(b,a);
r := b mod a;
m := x - u*q;
n := y - v*q;
b := a;
a := r;
x := u;
y := v;
u := m;
v := n;
od;
return [x,y];
end;
Now, regarding the recursive version I understand the logic but i have a
problem in implementing it (can't solve errors)
code:
extEuclidRecursive := function(a,b)
local q, x, y, r;
if b = 0 then
return [1,0];
fi;
q := QuoInt(b,a);
r := b mod a;
[x,y] := extEuclidRecursive(b,r);
return [x - q*y, y];
end;
I would appreciate it if the response was sooner rather than later. Thank
you for your time.
More information about the Forum
mailing list