Smallest Common Multiple. Dijkstra vs Euclid gcd

Smallest Common Multiple. Dijkstra vs Euclid gcd
0.0 0

#1

Tell us what’s happening:
I have 2 algorithms to find the gcd of 2 numbers: The Euclidian one and Dijkstra’s one.
These algorithms seem to give the same results (based on some manual tests).
However, if I use gcdDijk in the last line, the last test fails.
If I use gcdEuc, everything is fine and the tests all pass.
What am I not seeing, why doesn’t the solution that uses gcdDijk pass the tests?

Your code so far

function smallestCommons(arr) {
  //make range array from lowest to highest number in argument array
  var range= [];
  for(var i = Math.min(arr[0], arr[1]); i <= Math.max(arr[0], arr[1]); i++) {
    range.push(i);
  }
  
  // GCD Euclidean Algorithm
  function gcdEuc(x, y) {
	if (y === 0) {return x;}
	else {return gcdEuc(y, x%y);}
    }
  // GCD Dijkstra's Algorithm
  function gcdDijk(x, y) {
    if (x == y) {return x;}
    else if (x > y) {return gcdDijk(x-y, y);}
    else {return gcdDijk(x, y - x);}
  }
  
  //get scm of the current scm and the next element in the range array,
  //start scm as the first element in the range array
  return range.reduce((scm, val) => (scm * val) / gcdEuc(scm, val));
  //return range.reduce((scm, val) => (scm * val) / gcdDijk(scm, val));
}


smallestCommons([1,5]);

Your browser information:

Your Browser User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.113 Safari/537.36.

Link to the challenge:


#2

I’m not familiar with Dijkstra’s algorithm, but all tests pass anyway. Maybe you can point out what sort of output/error you got with the failing test?


#3

Your implementation is fine - the trouble with gcdDijk is the subtraction in the recursive step leads to very deep recursion if the difference between the two numbers is large - gcdEuc on the other hand uses modulo to drastically reduce the problem size in the recursive step

Looking at smallestCommons([23,18]) LCM(18, 19, 20, 21, 22) is 263340 - this means the last pair needs gcdDijk(263340, 23) - here’s what happens

gcdDijk(263340, 23) -> 263340 - 23 = 263317
  gcdDijk(263317, 23) -> 263317 - 23 = 263294
    gcdDijk(263294, 23) -> 263294 - 23 = 263271
       ...
// recursion continues for 263340/23 = 11449 calls

Each recursive call adds a frame to the javascript call stack - this slows down the browser and eventually javascript runs out of memory

btw gcd by repeated subtraction is Euclid’s original algorithm - Dijkstra used it as an example of how an algorithm could be derived/discovered simply by examining interesting properties of gcd

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.4.html

Its main advantage is it does not rely on division or multiplication or another “expensive” operation

Dijkstra uses recursive expressions while deriving the algorithm but his implementation is iterative - for the reason explained above

3.1) if a > b: GCD(a, b) = GCD(a - b, b) = GCD(a, a - b)
3.2) if a = b: GCD(a, b) = a = b
3.3) if a < b: GCD(a, b) = GCD(a, b - a) = GCD(b - a, b)


#4

A bit more on gcd by subtraction - it is easily written as a loop but I’ll use the recursive version to talk about Tail Recursion

This is gcd by recursive subtraction as written above by OP

function gcd(x, y) {
  if(x === y)
    return x
  if(x > y)
    return gcd(x - y, y)
  return gcd(x, y - x)
}

We’ve seen this causes deep recursion for large |x - y| because every recursive step reduces the problem by just one multiple of the smaller number

The recursion in gcd is special because both recursive calls occur at the end of their code paths in the function - also the return value of the recursive call is immediately returned without further processing - this is an example of tail recursion

It is special because tail recursion can be implemented under the covers in a way to bypass the actual function call and eliminate the cost of increasing the call stack - this is in fact a feature of the ES6 version of javascript called Tail Call Optimization or TCO - unfortunately TCO is not yet implemented in Chrome and maybe other browsers too

With TCO and "use strict", gcd above would not cause javascript to run out of memory

Interestingly we can manually simulate TCO in javascript with a trampoline function - the idea of a trampoline is a piece of code that allows program execution to jump from one context to another - for example application programs run low-level kernel system code via trampolines

A trampoline function for recursion is one that eliminates tail recursion by calling the real function repeatedly in a loop until the base case of the recursion is reached

Here’s the trampoline replacement for recursive gcd above

function trampoline(f) {  
  return (...a)=>{
// call provided function on variable number of parameters
    let r=f(...a)
// keep calling returned function while possible
    while(r instanceof Function) {
      r=r()
    }
    return r
  }
}

function gcd_tco(x, y) {
// gcd is recursive gcd with tail recursion
// gcd returns either a number for the recursive base case or
// a function that returns the value of a single recursive call
// the single tail recursive call merges the two cases of x>y and y>x
  const gcd=(x, y)=>x === y? x: ()=>gcd(Math.min(x, y), Math.abs(x-y))
// trampoline call simulates TCO
  return trampoline(gcd)(x, y)
}

The gcd_tco function wraps the call to the recursive gcd function inside trampoline - there is just one true recursive call - all other calls are intercepted and run inside the loop in trampoline

gcd_tco(263340, 23) runs in the blink of an eye with no issues with the call stack

gcd is still recursive with a slight twist - it only returns a value for the base case - it returns a function that returns the value of recursive call instead for the recursive case - this is for trampoline to know when to stop simulating the recursion

This may be too much for anyone starting out with recursion in javascript - the concepts are important though


#5

Thanks @ppc, this was very helpful!
I didn’t know the algorithm wasn’t created by Dijkstra and he just used it as an example.
I tested it with both numbers up to 1000 and the test coped fine.
I see how gcdDijk(263340, someOtherNumber) would cause the frame call stack to quickly get too big
edit: Woah, this is why that popular site is called stack-overflow.


#6

nice link to stack overflow!

side note on Dijkstra and recursion