Algorithms.js – Atwood's Law applied to CS101

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

by Envec83 • 12 years ago

59 34 12 years ago

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.

feliperibeiro5• 12 years 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• 12 years 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.

shoki5• 12 years ago

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

dtech• 12 years ago

Why is a Javascript implementation of some very basic algorithms interesting or noteworthy?...

eudox• 12 years ago

I think it's become some sort of elaborate joke.

teh_klev• 12 years ago

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.

feliperibeiro5• 12 years ago

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.

krat0sprakhar• 12 years ago

Whether 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

shoki5• 12 years ago

If you like doing this sort of thing, there are a million little CS problems like this codewars.com

One cool feature of the site is that you can vote on solutions; this lets you see a lot of neat solutions to problems, and learn a lot about how to write clean code.

shoki5• 12 years ago

Why not try to implement the iterative O(ln(n)) Fibonacci from SICP (Ex 1.19), rather than the old O(n) one? Or the Matrix exponentiation solution (he'd probably want to implement iterative matrix exponentiation too... doesn't look like he knows clearly how to do this)? https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

TheLoneWolfling• 12 years ago

Considering that the Fibonacci sequence is exponential, and hence the Nth Fibonacci number contains O(n) digits (well, in any sane base at least), you cannot compute the Nth Fibonacci number in under O(n) time.

shoki5• 12 years ago

Given the guys programming in Javascript and not using arbitrary precision arithmetic, he's always using 64 bits and representing his numbers as floating point, so I don't think you are reasoning correctly about the asympototic complexity here. I mean, if you really want to argue this, then to quote Leibniz: "Calculemus!"

The javascript solution presented does everything in O(n) arithmetic operations, and the SICP way does it in O(ln(n)) arithmetic operations (actually, there are a lot of ways to do it in O(ln(n)) operations).

thomasahle• 12 years ago

This reminds me of David Eppstein's fantastic PADS library [1] of algorithms implemented in Python.

[1] http://www.ics.uci.edu/~eppstein/PADS/

kaizeroskilo• 12 years ago

Why is this even on hn? Are you kidding me? I have some college projects too you know...

tambourine_man• 12 years ago

Great, let's see them

CmonDev2• 12 years ago

I see you are new to HN. Basically any old code re-implemented in is JS suddenly considered cool.

Example:

P: Look I have a spinning cube in 3d at 30 FPS!

HN: OMG, awesome, never done before!

bjourne• 12 years ago

Only the one who reinvents the wheel learns how it really works. :)

buttfacemcgee• 12 years ago

I've never invented a wheel but I'm pretty sure I know how it works

Algorithms.js – Atwood's Law applied to CS101

Related Stories