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 ?
-
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– Marc Rohloff2017年05月13日 17:46:14 +00:00Commented 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\$200_success– 200_success2017年05月13日 18:05:39 +00:00Commented May 13, 2017 at 18:05
1 Answer 1
Let me recommend a few general improvements before addressing the efficiency:
Naming:
- Change
Euclid
togcd
:- 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
toi
. Iteratorj
usually indicates a nested loop wherei
is the outer andj
the inner loop iterator.
Design:
Don't log outputs within the
Euclid
function. Removingconsole.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-conditionvar end = Math.min(m, n)
.It doesn't make sense to start the loop with
i = 1
and have a checki !== 1
in the loop body. Either start withi = 2
or better remove that check, as it causesEuclid(2, 3)
to output0
instead of1
.Also, end the loop when
i <= m
instead ofi < m
. This guarantees that e.g.Euclid(3, 3)
outputs3
instead of0
.
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;
}
-
\$\begingroup\$ That's a beautiful code. Thanks for pointing out the problems. I should have used a temp value as well. \$\endgroup\$Ozan– Ozan2017年05月13日 00:11:20 +00:00Commented May 13, 2017 at 0:11
-
\$\begingroup\$ @Ozan Using a temporary
end
orlength
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– le_m2017年05月13日 00:15:58 +00:00Commented May 13, 2017 at 0:15 -
1\$\begingroup\$ You could also use the more explanatory
var end = Math.min(n, m)
\$\endgroup\$Marc Rohloff– Marc Rohloff2017年05月13日 17:44:40 +00:00Commented May 13, 2017 at 17:44 -
\$\begingroup\$ @MarcRohloff I agree, edited the answer. Thanks! \$\endgroup\$le_m– le_m2017年05月13日 17:59:06 +00:00Commented 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\$Ozan– Ozan2017年05月13日 18:29:31 +00:00Commented May 13, 2017 at 18:29