Gcd (bc)

From LiteratePrograms

Jump to: navigation, search
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
Views
Personal tools