Algorithms.js – Atwood's Law applied to CS101

Re:Algorithms.js – Atwood's Law applied to CS101 by vog on Friday May 30, 2014 @08:59AM (#7821477)

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.

[ Parent | on HN ]

Re:Algorithms.js – Atwood's Law applied to CS101 by feliperibeiro on Friday May 30, 2014 @09:07AM (#7821511)

Still this is an issue with the algorithm, not the implementation.

http://en.wikipedia.org/wiki/Euclidean_algorithm

[ Parent | on HN ]

Re:Algorithms.js – Atwood's Law applied to CS101 by conistonwater on Friday May 30, 2014 @09:17AM (#7821555)

I 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 %.

[ Parent | on HN ]

Re:Algorithms.js – Atwood's Law applied to CS101 by feliperibeiro on Friday May 30, 2014 @09:29AM (#7821618)

You're right. This is the subtraction-based implementation, the division-based is the original and better one :)

https://github.com/felipernb/algorithms.js/commit/e5a04f9ad0...

[ Parent | on HN ]