[GAP Forum] Extended Euclid Algorithm Need HELP

[Stefan Kohl]

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
>