[GAP Forum] Extended Euclid Algorithm Need HELP
Stefan Kohl
stefan at mcs.st-and.ac.uk
Tue Nov 19 19:44:03 GMT 2013
Sam Johnson asked:
> 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?
The GAP Library already contains such function -- it is called Gcdex.
So there is no need to write your own code for this!
Hope this helps,
Stefan Kohl
> 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.
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>
More information about the Forum
mailing list