/*----------------------------------------------------------------------
  File    : euklid.c
  Contents: compute greatest common divisor with Euclid's algorithm
  Author  : Christian Borgelt
  History : 05.11.1997 file created
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

int gcd1 (int a, int b)
{                               /* --- recursive with subtraction */
  if (a == b)                   /* if the arguments are identical, */
    return a;                   /* any of them is their gcd */
  if (a > b)                    /* if a is larger, */
    return gcd1(a - b, b);      /* subtract b from a */
  else                          /* if b is larger, */
    return gcd1(a, b - a);      /* subtract a from b */
}  /* gcd1() */

/*----------------------------------------------------------------------
Note that this function works properly only for a > 0 and b > 0.
That this condition holds is made sure by a check in the main function.
For a proof that this algorithm works see:
Euclid, The Elements, book 7, paragraph 2.
----------------------------------------------------------------------*/

int gcd2 (int a, int b)
{                               /* --- recursive with remainder */
  if (a <= 0) return b;         /* if any argument is zero, */
  if (b <= 0) return a;         /* the other is the gcd */
  if (a > b)                    /* if a is larger, */
    return gcd2(a % b, b);      /* compute remainder of a / b */
  else                          /* if b is larger, */
    return gcd2(a, b % a);      /* compute remainder of b / a */
}  /* gcd2() */

/*--------------------------------------------------------------------*/

int gcd3 (int a, int b)
{                               /* --- iterative with subtraction */
  while (a != b) {              /* while the arguments differ */
    if (a > b) a -= b;          /* if a is larger, subtract b from a */
    else       b -= a;          /* otherwise subtract a from b */
  }
  return a;                     /* now a == b, so return any of them */
}  /* gcd3() */

/*----------------------------------------------------------------------
Note that this function works properly only for a > 0 and b > 0.
That this condition holds is made sure by a check in the main function.
  Exercise: Would it be more efficient to write the loop as
while (a != b) {
  while (a > b) a -= b;
  while (b > a) b -= a;
} ?
----------------------------------------------------------------------*/

int gcd4 (int a, int b)
{                               /* --- iterative with remainder */
  while ((a > 0) && (b > 0)) {  /* while both arguments are not zero */
    if (a > b) a %= b;          /* if a is larger, compute the */
    else       b %= a;          /* remainder of a / b, otherwise */
  }                             /* compute the remainder of b / a */
  if (a > 0) return a;          /* the variable that is not zero */
  else       return b;          /* is the greatest common divisor */
}  /* gcd4() */

/*--------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- comp. greatest common divisor */
  int a, b;                     /* numbers to compute gcd of */

  if (argc != 3) {              /* if wrong number of arguments given */
    printf("usage: %s a b\n", argv[0]);
    printf("compute the greatest common divisor of a and b "
           "with Euclid's algorithm");
    return 0;                   /* print usage message */
  }                             /* and abort function */
  a = atoi(argv[1]);            /* convert arguments to numbers and */
  b = atoi(argv[2]);            /* compute their greatest common div. */
  if ((a <= 0) || (b <= 0)) {   /* test for correct arguments */
    printf("%s: illegal arguments\n", argv[0]); return 1; }
  printf("gcd1(%i, %i) = %i\n", a, b, gcd1(a, b));
  printf("gcd2(%i, %i) = %i\n", a, b, gcd2(a, b));
  printf("gcd3(%i, %i) = %i\n", a, b, gcd3(a, b));
  printf("gcd4(%i, %i) = %i\n", a, b, gcd4(a, b));
  return 0;                     /* return 'ok' */
}  /* main() */

/*----------------------------------------------------------------------
Note that the number of arguments must be 3, since the first argument is
always the program's name (cf. program heron.c). This explains also, why
we ignore argv[0] (which contains the name) and convert only argv[1]
and argv[2] to numbers. Note also that this program does not detect
misspelled numbers. If it is called with 'euklid 3a7 5xx', then a will
be 3 and b will be 5 and no error reporting occurs.
----------------------------------------------------------------------*/