1

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?

Dream_Cap
  • 2,292
  • 2
  • 18
  • 30

2 Answers2

3

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

DAle
  • 8,990
  • 2
  • 26
  • 45
  • So this recursive function takes a lot less calls to come to the solution? – Dream_Cap Jan 26 '18 at 13:42
  • @Dream_Cap, a lot. Actually, it makes 2 calls. But it need not to be recursive, – DAle Jan 26 '18 at 13:45
  • Oh wow. I need to find a better way to visualize recursion. I'm finally taking an algorithms course, and there's a lot of recursion. But it seems like magic to me. I understand the base case, but not how the recursion builds up to a solution. – Dream_Cap Jan 26 '18 at 13:46
  • @Dream_Cap, the key is the division-based version of Euclidian algorithm https://en.wikipedia.org/wiki/Euclidean_algorithm. It can be either iterative or recursive, it doesn't matter. – DAle Jan 26 '18 at 13:50
  • Check this link https://www.calculatorsoup.com/calculators/math/lcm.php Try the numbers 226553150,1023473145 Your function gives a slightly different value. How do you handle such scenarios? – Flyn Sequeira Aug 21 '18 at 07:15
  • @FlynSequeira, I have no permission to access that calculator, anyway I suppose you are talking about floating point errors. We need some big integer library to get the correct result in js, for example, https://v8project.blogspot.com/2018/05/bigint.html – DAle Aug 21 '18 at 07:56
0

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 :)

Stefan Bobev
  • 161
  • 1
  • 6
  • Thanks for the info, but for my purposes, I'd really like to find out why my function is failing. This is an assignment I have, and I really have to figure out how to work with big numbers/integers. An lcm method like that is just taking the easy way out. – Dream_Cap Jan 26 '18 at 13:41