The smallest common multiple execution time and algorithm

Hi everyone! I recently did the “smallest common multiple” challenge. I did two different solutions and I know they must be very beginner level and slow. I wanted to know how slow they are and for the solutions provided by FCC, I want to know how fas they are.

As expected, my solutions did run slow. Curve fit for execution time ~ the larger number passed into function is around second degree polynomial.

Solution 4 provided by FCC is very stable, the execution time flattens out at around 100ms. However, the console always alerts about “Potential infinite loop detected on line 7. Tests may fail if this is not changed.”.
The code for Solution 4 is:

const smallestCommons = arr => {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  // Initially the solution is assigned to the highest value of the array
  let sol = max;

  for (let i = max - 1; i >= min; i--) {
    // Each time the solution checks (i.e. sol%i===0) it won't be necessary
    // to increment 'max' to our solution and restart the loop
    if (sol % i) {
      sol += max;
      i = max;
    }
  }
  return sol;
};

Solution 3 is very robust at smaller numbers. For example, if I call smallestCommons([1, 100]), execution time is around 0.9ms, comparing to 102ms for solution 4. But when I call bigger numbers, for example, smallestCommons([1, 250]), the console will say "RangeError: Maximum call stack size exceeded
".
The code for Solution 3 is:

function smallestCommons(arr) {
  // Euclidean algorithm for the greatest common divisor.
  // ref: https://en.wikipedia.org/wiki/Euclidean_algorithm
  const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));

  // Least Common Multiple for two numbers based on GCD
  const lcm = (a, b) => (a * b) / gcd(a, b);

  // range
  let [min, max] = arr.sort((a, b) => a - b);
  let currentLCM = min;

  while (min < max) {
    currentLCM = lcm(currentLCM, ++min);
  }

  return currentLCM;
}

Would anyone please help explain why Solution 4 has a potential infinite loop, and why Solution 3 cannot work at larger numbers? Thank you soooooo much!

P.S. These are my codes, I would also greatly appreciate if anyone would give some comments. Thank you so much!

The less slow one:

function smallestCommons(arr) {
    //sort the argument array and get the smaller number (m) and bigger number (n)
    let m = arr.sort((a, b) => a - b)[0];
    if (m == 1) {m = 2;}
    let n = arr.sort((a, b) => a - b)[1];
    //create a new 'factors' variable which equals to an array of integers ranging from 2 to n
    let factors = Array.from({length: n + 1}).map((_, i) => i).slice(2);
    //create a 'numbers' variable equal to a sequence of integers ranging from m to n;
    let numbers = factors.slice(m - 2, n - 1);
    //create a 'product' variable equal to the product of m through n, which may not be the smallest common multiple
    let product = numbers.reduce((accu, val) => accu * val);
    for (let index in factors) {
        let factor = factors[index];
        //if product divided by factor is still a common multiple, divide product by factor to get a smaller common multiple
        while(numbers.reduce((flag, val) => flag && (product / factor) % val == 0, true)) {
            product /= factor;
        }
        //filter away numbers that are multiple of the variable 'product'
        factors = factors.filter(val => val == factor || val % factor != 0);
    }
    return product;
 }

The more slow one (roughly two times slower):

function smallestCommons(arr) {
    //sort the argument array and get the smaller number (m) and bigger number (n)
    let m = arr.sort((a, b) => a - b)[0];
    let n = arr.sort((a, b) => a - b)[1];
    //create a new 'primes' variable which equals to an array of integers ranging from 2 to n
    let primes = Array.from({length: n + 1}).map((_, i) => i).slice(2);
    //filter 'primes' so that it contains prime number only
    for (let n in primes) {
        primes = primes.filter(num => num == primes[n] || num % primes[n] != 0);
    }
    //create a 'counts' variable which is an array of the same length with 'primes' array filled with 0
    let counts = Array(primes.length).fill(0);
    //prime factorization of integers through m to n
    //update 'counts' array with the highest count of each prime factor 
    for (let index in primes) {
        //prime factorization starts from the smallest prime number
        let prime = primes[index];
        //initialize a 'count' variable equal to 0, reprenting count of the prime number in factorization
        let count = 0;
        //primes factorization starts from number m and increment to n
        for (let j = m; j <= n; j++) {
            //copy j to num so that j will not be changed during the loop
            let num = j;
            //reset count to 0 for each new factorization on a new number
            count = 0;
            //prime factorization on the number 'num'
            while(num % prime == 0) {
                num /= prime;
                count += 1;
            }
            //update 'counts' array with the highest 'count' 
            if (count > counts[index]) {
                counts[index] = count;
            }
        }
    }
    //multiply 'primes' array and 'counts' array to get smallest common multiple
    return primes.reduce(function(multiple, prime, index) {return multiple * (prime ** counts[index]);}, 1)
}

Hello~!

Solution 4 trips the infinite loop protection alert not because there is an infinite loop, but because the protection kicks in when it thinks a loop might take more than 2500ms (or close to that, I’m not 100% sure of the exact value).

Solution 3 throws a Stack Size error because the gcd function is recursive. Recursive functions get dropped onto the stack until there are no more function calls, and then the stack gets executed. So the system is throwing an error because there are too many function calls in the stack. :slight_smile:

There is some discussion here on measuring performance and what makes code slow or fast.

Basically, two things are slow, excessive memory use and excessive calculations. Recursion can create excessive memory use. Not using the GCD can cause excessive calculations.

Update:

repl

https://repl.it/repls/ImpassionedBurlyTrees

code
// ********************************************************************************
// Least Common Multiple of Range demo and performance study
// ********************************************************************************
"use strict"

// --------------------------------------------------------------------------------
// Performance logging
// --------------------------------------------------------------------------------
const performance = require('perf_hooks').performance;

// --------------------------------------------------------------------------------
// Debug via console logging flag
// --------------------------------------------------------------------------------
const debug = false;

// --------------------------------------------------------------------------------
// Brief: Find least common multiple of a range
//
// Inputs:
//  arr - array containing lower and upper bound (inclusive)
//
// Outputs:
//  lcm - least common multiple of range
// --------------------------------------------------------------------------------
function smallestCommons(arr) {
  if (debug) console.log("WARNING - DEBUGGING LOGGING WILL DECREASE PREFORMANCE");

  // Compute GCD of two numbers
  function gcd(a, b) {
    // Loop until reduced
    while (b !== 0) {
      if (debug) console.log("GCD - a: " + a + " b: " + b);
      [a, b] = [b, a % b];
    }
    if (debug) console.log("GCD - final value: " + a);
    return a;
  }

  // Compute GCD of two numbers, with recursion
  //function gcd(a, b) {
  //  if (debug) console.log("GCD - a: " + a + "b: " + b);
  //  return (b === 0) ? a : gcd(b, a % b);
  //}

  // Compute LCM of two numbers
  function lcm(a, b) {
    if (debug) console.log("LCM - a: " + a + " b: " + b);
    return (a * b) / gcd(a, b);
  }

  // Loop over range
  const lower = Math.min(...arr);
  const upper = Math.max(...arr);
  let currentLCM = lower;
  for (let i = lower + 1; i <= upper; i++) {
    if (debug) console.log("Iteration - i: " + i)
    if (debug) console.rog("Current - currentLCM: " + currentLCM);
    currentLCM = lcm(i, currentLCM);
  }

  // Return
  if (debug) console.log("END DEBUGGING OUTPUT");
  return currentLCM;
}

// --------------------------------------------------------------------------------
// Performance testing
// --------------------------------------------------------------------------------
// Test cases
const maxMultiple = 4;
const numRuns = 25;
console.log("--------------------------------------------------");
console.log("Summary")
console.log(" - Number of Test Cases : " + maxMultiple);
console.log(" - Runs Per Test Case   : " + numRuns);
console.log("--------------------------------------------------\n\n");

for (let i = 1; i <= maxMultiple; i++) {
  /// Log test case
  const arr = [1, 50*i + 17];
  // Note: [1, 217] is the widest range with a result that isn't 'Infinity'
  console.log("--------------------------------------------------");
  console.log("Test Case " + i);
  console.log("--------------------------------------------------");

  // Multiple runs
  let lcm = 0;
  let times = [];
  for (let j = 0; j < numRuns; j++) {
    // Time execution
    const t0 = performance.now();
    lcm = smallestCommons(arr);
    const t1 = performance.now();

    // Log time elapsed
    times.push(t1 - t0);
  }

  // Compute stats
  const minTime = Math.min(...times);
  const maxTime = Math.max(...times);
  const avgTime = times.reduce((sum, item) => sum + item, 0) / numRuns;
  const variance = times.reduce((sumSqDiff, item) => sumSqDiff + (avgTime - item)**2, 0) / numRuns;
  const stdDev = Math.sqrt(variance);

  // Output
  console.log(" - Problem Values");
  console.log("     Lower              : " + arr[0]);
  console.log("     Upper              : " + arr[1]);
  console.log("     Result             : " + lcm);
  console.log(" - Statistics");
  console.log("     Average Time       : " + avgTime);
  console.log("     Minimum Time       : " + minTime);
  console.log("     Maximum Time       : " + maxTime);
  console.log("     Standard Deviation : " + stdDev);
  console.log("     Variance           : " + variance);
  console.log("--------------------------------------------------\n\n");

}

// ********************************************************************************

As far as I can tell, recursion isn’t really slower than iteration in Javascript nowadays (ES2015 added Tail Call Optimization) and can in some cases be faster. But in certain cases you can blow through the call stack and fail to return an answer with recursion while a loop returns an actual result.

Thank you both for your answers!

  1. So I suppose if there is really a need, one can manually change the stack size to achieve larger numbers with gcd method?
  2. As for the tail recursion, it takes me sometime to ingest your information since I am not computer background. Actually I still don’t fully understand tail recursion yet, but it seems (to me ) that the gcd function is already a tail recursion, so its call stack has already been optimised?

I don’t think that you can change the size of the call stack. That’s a memory limitation.

The GCD is tail recursion, which is why the recursive and iterative version of the GCD function in my code take the same amount of time.