Skip to content

Instantly share code, notes, and snippets.

@nkapliev
Last active Sep 9, 2016
Embed
What would you like to do?
Greatest common divisor in Javascript @see: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
var gcd = function(a, b) {
var coef = 1;
while (
a !== b &&
a !== 0 &&
b !== 0 &&
a !== 1 &&
b !== 1
) {
if ( ! (a % 2) && ! (b % 2)) {
coef *= 2;
a /= 2;
b /= 2;
} else if ( ! (a % 2)) {
a /= 2;
} else if ( ! (b % 2)) {
b /= 2;
} else if (a > b) {
a = (a - b) / 2;
} else if (b > a) {
b = (b - a) / 2;
}
}
return coef * ((a === 1 || b === 1) ? 1 : (a || b));
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment