Extended Euclidean algorithm

Here is a JavaScript implementation which should work in most browsers:

// This program works only for non-negative inputs. // Get data from user and convert strings to integers. var a = parseInt(prompt("Enter non-negative value for a",0)) var b = parseInt(prompt("Enter non-negative value for b",0))

// Save original values. a0 = a; b0 = b;

// Initializations. We maintain the invariant p*a0 + q*b0 = a and r*a0 + s*b0 = b. p = 1; q = 0; r = 0; s = 1;

// The algorithm: while (b != 0) {

 c = a % b;
 quot = Math.floor(a/b);  //Javascript doesn't have an integer division operator
 a = b;
 b = c;
 new_r = p - quot * r; new_s = q - quot * s;
 p = r; q = s;
 r = new_r; s = new_s;

}

// Show result. alert("gcd(" + a0 + "," + b0 + ")=" + a + " " + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)

When analyzing the runtime of this version of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case requires O(n) divisions, where n is the number of digits in the input (see Big O).