0
\$\begingroup\$

I was reading Donald Knuth's Art of Computer Programming and it occurred to me that I should also code along while reading.

function Euclid(m,n){
  var greatestDivider = 0;
  if(m > n){
    for(var i = 1; i < m; i++){
      if(m % i === 0 && n % i === 0 && i !== 1){
        greatestDivider = i;
      }
    }
  }else {
    for(var j = 1; j < n; j++){
      if(m % j === 0 && n % j === 0 && j !== 1) {
        greatestDivider = j;
      }
    }
  }
 console.log('common divisor is : ' + greatestDivider);

}
Euclid(30,90);

Is it efficient to employ the algorithm in such a way ?

\$\endgroup\$
  • 1
    \$\begingroup\$ One comment in addition to le_m's answer, it might be quicker to count down and stop on the first match rather than counting up and testing every possible value. \$\endgroup\$ – Marc Rohloff May 13 '17 at 17:46
  • \$\begingroup\$ @MarcRohloff Comments are for seeking clarification to the question, and may be deleted. Please put all suggestions for improvements in answers, even trivial ones. \$\endgroup\$ – 200_success May 13 '17 at 18:05
3
\$\begingroup\$

Let me recommend a few general improvements before addressing the efficiency:

Naming:

  • Change Euclid to gcd:
    • Lower case initial letter for function names.
    • gcd is the common term for greatest common divisor, the Euclidean algorithm is just one possible implementation. And you are not implementing the Euclidean algorithm.
    • Rename the second loop iterator j to i. Iterator j usually indicates a nested loop where i is the outer and j the inner loop iterator.

Design:

  • Don't log outputs within the Euclid function. Removing console.log makes it a pure, side-effect free function. Those are much easier to reason about.

  • Remove the outer if ... else and get rid of the duplicate code by precomputing a common for-loop test-condition var end = Math.min(m, n).

  • It doesn't make sense to start the loop with i = 1 and have a check i !== 1 in the loop body. Either start with i = 2 or better remove that check, as it causes Euclid(2, 3) to output 0 instead of 1.

  • Also, end the loop when i <= m instead of i < m. This guarantees that e.g. Euclid(3, 3) outputs 3 instead of 0.

This is your code with above suggestions applied:

function gcd(m, n) {
  var result = 0;

  for (var i = 1, end = Math.min(m, n); i <= end; i++) {
    if (m % i === 0 && n % i === 0) {
      result = i;
    }
  }

  return result;
}

This implementation is pretty slow. The modulo operator has the same performance penalty as the division operator. Also, your implementation only works with positive arguments.

This is the actual Euclidean algorithm (division variant):

function gcd(a, b) {
  while (b !== 0) {
     var t = b; 
     b = a % b;
     a = t;
  }
  return a;
}
\$\endgroup\$
  • \$\begingroup\$ That's a beautiful code. Thanks for pointing out the problems. I should have used a temp value as well. \$\endgroup\$ – Ozan May 13 '17 at 0:11
  • \$\begingroup\$ @Ozan Using a temporary end or length variable is a pretty common 'micro-optimization'. Some prefer to move this declaration out of the loop initializer. The advantage here is: You have only a single path of execution, which allows the compiler to detect and optimize 'hotspots' earlier. Also, the code is more DRY (don't repeat yourself). \$\endgroup\$ – le_m May 13 '17 at 0:15
  • 1
    \$\begingroup\$ You could also use the more explanatory var end = Math.min(n, m) \$\endgroup\$ – Marc Rohloff May 13 '17 at 17:44
  • \$\begingroup\$ @MarcRohloff I agree, edited the answer. Thanks! \$\endgroup\$ – le_m May 13 '17 at 17:59
  • \$\begingroup\$ What really confuses me most of the time when I code in JavaScript is the fact that the arrow function resembles <= a lot and yet the other way around is >= but somehow I end up mixing >= with => when I use for loops. \$\endgroup\$ – Ozan May 13 '17 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.