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 ?

asked May 12, 2017 at 23:26
\$\endgroup\$
2
  • 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\$ Commented May 13, 2017 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\$ Commented May 13, 2017 at 18:05

1 Answer 1

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;
}
answered May 13, 2017 at 0:07
\$\endgroup\$
5
  • \$\begingroup\$ That's a beautiful code. Thanks for pointing out the problems. I should have used a temp value as well. \$\endgroup\$ Commented May 13, 2017 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\$ Commented May 13, 2017 at 0:15
  • 1
    \$\begingroup\$ You could also use the more explanatory var end = Math.min(n, m) \$\endgroup\$ Commented May 13, 2017 at 17:44
  • \$\begingroup\$ @MarcRohloff I agree, edited the answer. Thanks! \$\endgroup\$ Commented May 13, 2017 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\$ Commented May 13, 2017 at 18:29

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.