Algorithms.js – Atwood's Law applied to CS101
1–10 of 36 posts
Re: Algorithms.js – Atwood's Law applied to CS101
#2The commit message "Optimized performance of the GCD algorithm" piqued my interest. It's GCD, what's there to optimize?
I noticed the following code:
while (b !== 0) { if (a > b) { a -= b; } else { b -= a; } }
Please don't do this in your code. If there is a built it instruction for division with remainder, don't reimplement it poorly in javascript.
Re: Algorithms.js – Atwood's Law applied to CS101
#3The commit message "Optimized performance of the GCD algorithm" piqued my interest. It's GCD, what's there to optimize? I noticed the following code: while (b !== 0) { if (a > b) { a -= b; } else { b -= a; } } This uses repeated subtraction (a -= b) to implement division with remainder (a %= b); imagine a=1e12+1, b=2. Please don't do this in your code. If there is a built it instruction for division with remainder, d…
This is the Euclidean algorithm for GCD, it's naive and simple. But if you see it more carefully, the commit that says "Optimized performance ..." contains just the lines:
34 var tmp = a;
35 a = Math.max(a, b);
36 b = Math.min(tmp, b);
37 if (a % b === 0) return b;
Re: Algorithms.js – Atwood's Law applied to CS101
#4Why is a Javascript implementation of some very basic algorithms interesting or noteworthy?...
Re: Algorithms.js – Atwood's Law applied to CS101
#5Whether its Javascript or any other language, I think writing algorithms is a great way of driving home certain concepts when you are learning algorithms. Its even more fun to use your data structures and algorithms to solve toy problems and see the difference. Obviously, this is not recommended in production where one must use battle-tested code.
I did a similar exercise when I was doing a course on Coursera in Python - https://github.com/prakhar1989/Algorithms
Re: Algorithms.js – Atwood's Law applied to CS101
#6Why is a Javascript implementation of some very basic algorithms interesting or noteworthy?...
I think it's become some sort of elaborate joke.
Re: Algorithms.js – Atwood's Law applied to CS101
#7The commit message "Optimized performance of the GCD algorithm" piqued my interest. It's GCD, what's there to optimize? I noticed the following code: while (b !== 0) { if (a > b) { a -= b; } else { b -= a; } } This uses repeated subtraction (a -= b) to implement division with remainder (a %= b); imagine a=1e12+1, b=2. Please don't do this in your code. If there is a built it instruction for division with remainder, d…
This is the Euclidean algorithm for GCD, it's naive and simple. But if you see it more carefully, the commit that says "Optimized performance ..." contains just the lines: 34 var tmp = a; 35 a = Math.max(a, b); 36 b = Math.min(tmp, b); 37 if (a % b === 0) return b; to avoid the unnecessary repetitions if b is already the GCD
Still, this wouldn't help in the given case of a=1e12+1, b=2. What's the point of those four lines 34-37 -- these would be unnecessary if the code used "%" instead of "-" in the first place.
Edit: Also, if you stick to the original subtraction-based version of the algorithm, why adding that other optimization? That wasn't part of the original algorithm, either. This seems to be double standard.
Re: Algorithms.js – Atwood's Law applied to CS101
#8Why is a Javascript implementation of some very basic algorithms interesting or noteworthy?...
See: http://blog.codinghorror.com/the-principle-of-least-power/
"Atwood's Law: any application that can be written in JavaScript, will eventually be written in JavaScript."
It's kind of a joke thing.
Re: Algorithms.js – Atwood's Law applied to CS101
#9Earlier quoted context omitted.
This is the Euclidean algorithm for GCD, it's naive and simple. But if you see it more carefully, the commit that says "Optimized performance ..." contains just the lines: 34 var tmp = a; 35 a = Math.max(a, b); 36 b = Math.min(tmp, b); 37 if (a % b === 0) return b; to avoid the unnecessary repetitions if b is already the GCD
Still, this wouldn't help in the given case of a=1e12+1, b=2. What's the point of those four lines 34-37 -- these would be unnecessary if the code used "%" instead of "-" in the first place. Edit: Also, if you stick to the original subtraction-based version of the algorithm, why adding that other optimization? That wasn't part of the original algorithm, either. This seems to be double standard.
Still this is an issue with the algorithm, not the implementation.
Re: Algorithms.js – Atwood's Law applied to CS101
#10Why is a Javascript implementation of some very basic algorithms interesting or noteworthy?...
See: http://blog.codinghorror.com/the-principle-of-least-power/ "Atwood's Law: any application that can be written in JavaScript, will eventually be written in JavaScript." It's kind of a joke thing.
Exactly! Also, many JS devs are clueless about CS101 basic things, it's a way to maybe make them a bit interested.
From the wiki (https://github.com/felipernb/algorithms.js/wiki):
The intention is to blend academic concepts with the
JavaScript bits of insanity, applying Atwood's Law to CS101.