4 ms·
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
by feliperibeiro 12y ago
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
- vog 12y agoStill, 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.
- feliperibeiro 12y agoStill this is an issue with the algorithm, not the implementation. http://en.wikipedia.org/wiki/Euclidean_algorithm http://en.wikipedia.org/wiki/Euclidean_algorithm
- conistonwater 12y agoI think you misunderstood the Euclidean algorithm. The basic iteration is of the form gcd(a, b) = gcd(b, a mod b), and there is no need to compute mod with anything other than %.
- feliperibeiro 12y agoYou're right. This is the subtraction-based implementation, the division-based is the original and better one :) https://github.com/felipernb/algorithms.js/commit/e5a04f9ad07256ef5cd86aa2fc772dc713381de3 https://github.com/felipernb/algorithms.js/commit/e5a04f9ad0...
- shoki 12y agoThere are a couple of GCD algorithms that have better asymptotic performance than Euclid's (an old one is due to Knuth): http://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02017-0/ http://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-0... I'm surprised the author didn't implement the binary gcd, however, although it has the same big-O as Euclid: https://en.wikipedia.org/wiki/Binary_GCD_algorithm https://en.wikipedia.org/wiki/Binary_GCD_algorithm
- feliperibeiro 12y agoI've been doing this sporadically and in my free time, just for fun, so there are a lot of fundamental things that haven't been covered there. :)
- shoki 12y agoI do this sort of thing sporadically in my free time too... it's still good to go back and do stuff smarter when you learn better rather than accepting whatever they taught you in CS101 as the end of the story.