Hacker News Reader

Comment by conistonwater | Hacker News Reader

The 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, don't reimplement it poorly in javascript.

View on HN

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.

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

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

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

There 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-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

I'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. :)

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

Reply on news.ycombinator.com