# Smallest Common Multiple. Dijkstra vs Euclid gcd

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?

``````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 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`.

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?

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)

2 Likes

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

1 Like

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.