Gcd (bc)

From LiteratePrograms

Other implementations: bc | C

This implements the Euclidean Algorithm in the bc to find the Greatest Common Divisor of two integers 'a' and 'b'.

define gcd(a,b) {
  auto q,r;
  while(b != 0) {
    r=a % b;
    a=b;
    b=r;
  }
  return(a);
}

Alternatively, we can write this more clearly:

define gcd(numerator,denominator) {
  auto quotient, remainder;
  scale=0;
  while(denominator != 0) {
    quotient    = numerator / denominator;
    remainder   = numerator % denominator;
    numerator   = denominator;
    denominator = remainder;
  }
  return(numerator);
}

The scale is set to zero so that bc will perform modulo operations correctly.

Here is another implementation of the Greatest Common Divisor that shows every step used.

define gcdsteps(a,b) {
  auto q,r;
  print "a=b*q+r\n"
  while(b != 0) {
    q=a/b;
    r=a%b;
    print a,"=",b,"*",q,"+",r,"\n";
    a=b;
    b=r;
  }
  print "0=",b,"*",q,"+",r,"   -- STOP\n";
  return(a);
}

Download code