3 ms·
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 "%" inst
by vog 12y ago
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.
- 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...