CODEWITHSUNDEEP
javascriptalgorithm
Dream_Cap
Dream_Cap

Reputation: 2302

Javascript least common multiple function is failing for very large numbers

I have an lcm function that is failing for very large numbers, but not smaller numbers. For example, on an input of (6, 8), it returns 24 as the lcm. But if I do something such as (2000000000,1999999999), my while loop will infinitely loop, and not return anything.

I am using a big integer library to handle big numbers, but it doesn't seem to be working. Here is the code: 

function lcm(n1, n2) {

  n1 = bigInt(n1).value; //bigInt comes from the big-integer library
  n2 = bigInt(n2).value;

  let smaller = bigInt.min(n1, n2);
  let bigger = bigInt.max(n1, n2);
  let s1 = smaller;

  if (smaller === 1) { 
    return bigger;
  } else if (bigger === 1) {
    return smaller;
  }

  while (s1 % bigger !== 0) { //once s1 % bigger is 0, we found the lcm in s1's variable

    s1 = bigInt(s1).add(smaller);
    console.log(s1);

  }
  return s1;
}

Any ideas?

Upvotes: 1

Views: 345

Answers (2)

DAle
DAle

Reputation: 9117

Your algorithm is too slow. With n1=2000000000 and n2=1999999999 it is doing 2 billion add calls. You can use this formula:

lcm(a, b) = a * b / gcd(a, b)

To calculate gcd(a, b) (greatest common divisor) you need to implement division-based version of Euclidian algorithm. Recursive implementation:

function gcd(a, b) {
    return b == 0 ? a : gcd(b, a % b);
}

Other implementations (if you want to avoid recursion) can be found here: JS how to find the greatest common divisor

Upvotes: 3

Stefan Bobev
Stefan Bobev

Reputation: 171

If you are using this package, then you are in luck - it has a built in lcm method for you: link to the docs

If you want to see the implementation of it, check out the source over at the Github repository.

Implementation of the method inside the above library: Source

Hope this helps you out :)

Upvotes: 0

Related Questions