/*
 * Ambrose Sterr
 * 04/18/06
 * Euclid's Algorithm for finding the greatest common denominator of two
 * numbers.
 * Usage: gcd <#1> <#2>
 * #1 is the first number
 * #2 is the second number
 *
 * The program is constant-time except for recurse, which is polynomial in runtime as long as % is polynomial (which it is).
 * Because a%b < b, each successive run of recurse has a b(n+1) <= b(n)-1, so it will take no more than b steps to reach b == 0.
 * So the runtime O(n*O(a%b)), which is polynomial.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void main(int argc, char* argv[])
{
    if (argc != 3)
    {
        printf("Wrong number of arguments!\nUsage: gcd <#1> <#2>\n");
        exit(0);
    }
    else
    {
        int gcd = recurse(atoi(argv[1]), atoi(argv[2]));
        printf("The greatest common denominator of %s and %s is %d.\nThis program took %d clock cycles.", argv[1], argv[2], gcd, clock());
    }
}
int recurse(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return recurse(b, a % b);
    }
}