Skip to content

Test Program 2 : Extended Euclid algorithm (iterative version and with functions)ΒΆ

This test program calculates the GCD (Greatest Common Divisor) of two numbers along with Bezout co-efficients. (iterative version)

Input

Two numbers

Output

GCD of the given two numbers and Benoud co-efficients.

This program test the iteration, parameter passing, passing of user-defined datatype as return value of function.

decl
 int ExtendedEuclid(int a,int b);
enddecl

int ExtendedEuclid(int a,int b)
{
 decl
  int r0,r1,s0,s1,t0,t1,qi,ri,si,ti;
 enddecl

 begin
  r0 = a;
  r1 = b;
  s0 = 1;
  s1 = 0;
  t0 = 0;
  t1 = 1;

  while(r1 != 0) do
   qi = r0/r1;
   ri = r0 - (qi*r1);
   si = s0 - (qi*s1);
   ti = t0 - (qi*t1);
   r0 = r1;
   r1 = ri;
   s0 = s1;
   s1 = si;
   t0 = t1;
   t1 = ti;
  endwhile;

  write(r0);
  write(s0);
  write(t0);

  return 0;
 end
}

int main()
{
 decl
  int a,b,c;
 enddecl

 begin
  read(a);
  read(b);
  c = ExtendedEuclid(a,b);
  return 0;
 end 
}