57

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

Anyone done that before and willing to share?

alex
  • 479,566
  • 201
  • 878
  • 984
bboy
  • 1,357
  • 2
  • 15
  • 31

3 Answers3

115

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.

Maxik
  • 18
  • 5
alex
  • 479,566
  • 201
  • 878
  • 984
  • 8
    recursive isn't the fastest. – Florian F Nov 10 '14 at 14:22
  • 19
    @FlorianF Okay, thanks for that. I missed where the OP asked for the fastest solution possible. – alex Nov 11 '14 at 05:50
  • 10
    He didn't ask. I want to warn people against using this method in real-life programs. – Florian F Nov 11 '14 at 08:34
  • 7
    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 –  Feb 15 '15 at 09:28
  • 14
    @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. :-) – T.J. Crowder Nov 15 '15 at 13:30
  • 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? – Squirrl Dec 10 '15 at 04:19
  • I got http://jsfiddle.net/a9awqptx/ – Squirrl Dec 10 '15 at 04:40
  • @Squirrl Here's some code for multiple numbers: https://jsfiddle.net/xyx86q5u/ – Travis Kriplean Jan 01 '18 at 18:06
  • @KoenDoodeman Here is an even slightly shorter one-liner: `var gcd = function(a,b) { return b ? gcd(b,a%b) : a; };` – Waruyama Oct 01 '18 at 08:08
  • 3
    `const gcd = (a,b) => !b ? a : gcd(b,a%b)` – noobninja Mar 04 '19 at 00:07
  • 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));` – Yousef Amar Jan 30 '20 at 17:42
  • 2
    Worth noting that tail call optimization still isn’t widely available and has even been removed from Node: https://kangax.github.io/compat-table/es6/ – Jordan May 06 '20 at 11:03
  • 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 – Werlious Apr 28 '21 at 05:15
  • 1
    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; }` – JamesTheAwesomeDude Sep 15 '22 at 22:01
  • 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). – Aleksandr Hovhannisyan Mar 12 '23 at 17:28
31

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
Yannis
  • 6,047
  • 5
  • 43
  • 62
18
function egcd(a, b) {
    if (a == 0)
        return b;

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

    return a;
}
Amani
  • 519
  • 2
  • 5