// Implementing the Euclidean algorithm.
//
// Ethan Bolker
// October, 2008 for cs320
//
// algorithm courtesy of 
// http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
// (I could have done it myself but this was quicker.)

public class Euclid
{
    private int m;
    private int n;
    private int a;
    private int b;
    private int d;
    private int steps;
    private double log2bound;

    /** 
     *  Euclid constructor.
     *
     *  @param m the first integer
     *  @param m the second integer
     *  @exception NumberFormatException if both m and n are 0
     */
    public Euclid( int m, int n )
    {
	if ((m==0 && n==0)) {
	    throw new NumberFormatException();
	}
	log2bound = Math.ceil(
	      Math.log(Math.max(Math.abs(m), Math.abs(n)))/0.6931);
	this.m = m;
	this.n = n;
	steps = 0;
	// now do the work
	d = m;
	a = 1;
	b = 0;
	int nexta = 0;
	int nextb = 1;
	int q;
	int r = m;
	while (n != 0 ) {
	    d = r;
	    q = m/n; // integer arithmetic truncates
	    r = m%n;

	    m = n; // changes only local copy of m, not this.m
	    n = r;

	    int tmp = nexta;
	    nexta = a - q*nexta;
	    a = tmp;
	    
	    tmp = nextb;
	    nextb = b - q*nextb;
	    b = tmp;

	    ++steps;
	}
    }
    
    // getters for all numbers of interest
    public int getM() { return m; }
    public int getN() { return n; }
    public int getA() { return a; }
    public int getB() { return b; }
    public int getD() { return d; }
    public int getSteps() { return steps; }
    
    public String toString()
    {
	return "gcd( " + getM() + ", " + getN() + ") = " + getD() +
	    " = " + 
	    getA() + "*" + getM() + " + " + getB() + "*" + getN() +
	    "\nsteps: " + getSteps() +
	    "\nlog2(max(m,n)): " + log2bound;
    }
    

    public static void main( String[] args )
    {
	int m = 0;
	int n = 0;
	Euclid euclid = null;

	// collect arguments
	try {
	    m = Integer.parseInt(args[0]);
	    n = Integer.parseInt(args[1]);	    
	}
	catch( Exception e ) {
	    System.out.println("usage: java Euclid m n");
	    System.exit(0);
	}
	// create new Euclid object to compute answers
	try {
	    euclid = new Euclid(m,n);
	}
	catch( NumberFormatException e ) {
	    System.out.println("m and n can't both be 0");
	    System.exit(1);
	}
	System.out.println(euclid);
    }
    
}