 # 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);
if (m == 1) {m = 2;}
let n = arr.sort((a, b) => a - b);
//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);
let n = arr.sort((a, b) => a - b);
//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. 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);
console.log("     Upper              : " + arr);
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.