JS how to find the greatest common divisor [closed]

Question

I would like to find the greatest common divisor using JavaScript.

Anyone done that before and willing to share?

Sardonic

Answer 1

Here is a recursive solution, using the Euclidean algorithm.

 var gcd = function(a, b) {
  if (!b) {
    return a;
  }

  return gcd(b, a % b);
}

Our base case is when b is equal to 0. In this case, we return a.

When we're recursing, we swap the input arguments but we pass the remainder of a / b as the second argument.

Worm

recursive isn't the fastest. – Investigate

@FlorianF Okay, thanks for that. I missed where the OP asked for the fastest solution possible. – Worm

He didn't ask. I want to warn people against using this method in real-life programs. – Investigate

This code can be written in a single line by saying var gcd = function(a,b) { return (!b)?a:gcd(b,a%b); };. Nice solution by the way, +1 – Vo

@FlorianF: Now that the ES2015 (aka ES6) specification requires tail-call optimization, it won't really be recursion anymore once engines are up to spec. :-) – Him

Awesome function. Sorry if this is a dumb question, but how can I apply this to find the gcd of multiple numbers, instead of just two? – Gangue

I got jsfiddle.net/a9awqptx – Gangue

@Gangue Here's some code for multiple numbers: jsfiddle.net/xyx86q5u – Muscarine

@KoenDoodeman Here is an even slightly shorter one-liner: var gcd = function(a,b) { return b ? gcd(b,a%b) : a; }; – Panties

const gcd = (a,b) => !b ? a : gcd(b,a%b) – Ns

Here's a one-liner that that can take as many numbers as you want as arguments: const gcd = (...n) => n.length === 2 ? n[1] ? gcd(n[1], n[0] % n[1]) : n[0] : n.reduce((a, c) => a = gcd(a, c)); – Halfprice

Worth noting that tail call optimization still isn’t widely available and has even been removed from Node: kangax.github.io/compat-table/es6 – Boatbill

I would advise against using recursive calls unless you really know what your doing. Recursive operations can overflow the stack if your not careful, while an iterative solution would continue to happily use up all the cpu it can to find the answer. They have their pros and cons, but like I said, I'd advise against unless you know what your doing – Hippolytus

I think Safari is the only modern browser that does TCO. If you don't want to destroy RAM on FF/Chrome, this is trivially fixed: function gcd(a, b) { while (b) { [a, b] = [b, a % b]; } return a; } – Custos

You need to take the absolute value of a and b because JavaScript's modulo operator incorrectly returns negative numbers, whereas in math remainders are always >= 0. For example, with this solution, gcd(-5, -15) = -5, but the true gcd is always a natural number (in this case, 5). – Thoroughwort

Answer 2

Taken from Wikipedia.

Recursive:

function gcd_rec(a, b) {
    if (b) {
        return gcd_rec(b, a % b);
    } else {
        return Math.abs(a);
    }
}

Iterative:

function gcd(a,b) {
    a = Math.abs(a);
    b = Math.abs(b);
    if (b > a) {var temp = a; a = b; b = temp;}
    while (true) {
        if (b == 0) return a;
        a %= b;
        if (a == 0) return b;
        b %= a;
    }
}

• EDITed per user's comment

Joaquin

if (a < 0) a = -a; You can also do a = Math.abs(a); (same for the next line) – Supererogation

Answer 3

function egcd(a, b) {
    if (a == 0)
        return b;

    while (b != 0) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}

Podgorica

please add explanation of your code. – Infinitude

This implementation is really really slow, there's really no good reason to use repeated subtraction rather than modulus. Calling egcd(1000000002, 4) will take several seconds and send your fan spinning out of control because it is doing 250 million subtractions, before finally spitting out: 2 – Reclaim