/*
* GCD -- compute the greatest common divisor of two integers recursively
*
* Usage: gcd
*
* Inputs: Integers m, n
* Outputs: gcd(m, n) = g -- m, n as above; g is gcd(m, n)
* Errors: - m, n not an integer
*
* Assumptions: - the arguments are not digits followed by non-digits
* (unchecked)
* - at least 1 of m, n is non-zero (checked)
*
* Matt Bishop, ECS 36A
* October 17, 2019 -- wrote original version
*/
#include
/*
* GCD -- compute the GCD of m and n recursively
* Parameters: m, n 2 integers of which at least 1 is non-zero
* Returns: gcd of m and n
* Assumptions: - at least 1 of m, n is non-zero (not checked)
* - neither m, n are negative (not checked)
* Algorithm: Euclid's Algorithm, using the relation:
* gcd(m, n) = gcd(n, n - m)
*
*/
int gcd(int m, int n)
{
/* base case */
if (n == 0) return(m);
/* recursive case */
return(gcd(n, m % n));
}
/*
* main ro
*/
int main(void)
{
int rv; /* success of failure of read */
int ch; /* character to discard */
int m, n; /* numbers to compute the gcd of */
int badct = 0; /* number of bad arguments */
/*
* loop through the argument list
*/
printf("> ");
while((rv = scanf("%d,%d", &m, &n)) != EOF){
if (rv != 2){
fprintf(stderr, "Invalid input\n");
/* discard the rest of the line */
while((ch = getchar()) != '\n' && ch != EOF)
;
/* quit on EOF; loop on error */
if (ch == EOF)
return(badct);
badct++;
printf("> ");
continue;
}
/*
* now check error conditions and other things
*/
/* if both m, n are 0, the gcd is undefined */
if (m == 0 && n == 0){
fprintf(stderr, "need at least 1 non-zero argument\n");
printf("> ");
continue;
}
/* handle negative numbers; gcd of negatives is same */
/* as gcd of positives with same absolute values */
if (n < 0) n = -n;
if (m < 0) m = -m;
/*
* all's right with the world
* compute and print the GCD
*/
printf("gcd(%d, %d) = %d\n", m, n, gcd(m, n));
/* reprompt */
printf("> ");
}
/*
* return exit code of the number of failures
*/
return(badct);
}