[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