/******************************************************** * A short Java program to find the GCD of two integers. * The "error checking" part of the code is significantly * longer than the actual code to find the GCD itself. * * The program should be invoked with two integer * arguments like * * java GCD 230 64 * * The error checking consists of verifying there are at * least two (integer) arguments (and that these are the * first arguments given to the program), and that the * two inputs are not both 0, as gcd(0,0) is not defined. * * Runnig time: * Since this is really just a straightforward * implementation of the Extended Euclidean * algorithm, as described in the lecture notes, the * running time of this algorithm is O(log (max ({a, b})). *********************************************************/ import java.io.*; import java.util.*; class GCD { public static void main (String args[]) // entry point from OS { int a=0, b=0, d; int sign_a = 1, sign_b = 1; // These are used to handle cases when a < 0 // and/or b < 0, as the extendedEuclid function // assumes that a and b are nonnegative. int[] ans = new int[3]; /* Check for errors, see if user gave enough arguments, etc. */ if (args.length < 2) { System.out.println("\n Please input two arguments!\n"); System.exit(1); } else if (args.length > 0) { try { a = Integer.parseInt(args[0]); } catch (NumberFormatException e) { System.err.println("\n Arguments must be integers!\n"); System.exit(1); } try { b = Integer.parseInt(args[1]); } catch (NumberFormatException e) { System.err.println("\n Arguments must be integers!\n"); System.exit(1); } } /* end of "if" block to catch input errors */ /* Check for input of two zeros, and print error if that's that case */ if ((a == 0) && (b == 0)) { System.out.println("\n Oops, both arguments are zero! No GCD of zero!\n"); System.exit(1); } /* If a and/or b is negative, then track this information for later output, because the extendedEuclid function expects nonnegative input. */ if ( a < 0 ) { sign_a = -1; a = Math.abs(a); } if ( b < 0 ) { sign_b = -1; b = Math.abs(b); } /* Find the answer and print it out */ ans = ExtendedEuclid(a,b); System.out.println("\n gcd(" + a*sign_a + "," + b*sign_b +") = " + ans[0]); System.out.print(" " + ans[0] + " = (" + sign_a*ans[1] + ") (" + sign_a*a +")"); System.out.println(" + (" + sign_b*ans[2] + ") (" + sign_b*b + ")\n"); } public static int[] ExtendedEuclid(int a, int b) /* This function will perform the Extended Euclidean algorithm to find the GCD of a and b. We assume here that a and b are non-negative (and not both zero). This function also will return numbers j and k such that d = j*a + k*b where d is the GCD of a and b. */ { int[] ans = new int[3]; int q; if (b == 0) { /* If b = 0, then we're done... */ ans[0] = a; ans[1] = 1; ans[2] = 0; } else { /* Otherwise, make a recursive function call */ q = a/b; ans = ExtendedEuclid (b, a % b); int temp = ans[1] - ans[2]*q; ans[1] = ans[2]; ans[2] = temp; } return ans; } } /* end of "main" program */