Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithms.js – Atwood's Law applied to CS101

github.com

Post reply on HN
Print view View original

11–20 of 36 posts

Re: Algorithms.js – Atwood's Law applied to CS101

#11

Post by shoki »

feliperibeiro wrote: post #3
conistonwater wrote: post #2

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, d…

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

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

Re: Algorithms.js – Atwood's Law applied to CS101

#12

Post by conistonwater »

feliperibeiro wrote: post #9
vog wrote: post #7

Earlier quoted context omitted.

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

Re: Algorithms.js – Atwood's Law applied to CS101

#13

Post by shoki »

krat0sprakhar wrote: post #5

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 Pyth…

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.

Re: Algorithms.js – Atwood's Law applied to CS101

#14

Post by feliperibeiro »

conistonwater wrote: post #12
feliperibeiro wrote: post #9

Earlier quoted context omitted.

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

Re: Algorithms.js – Atwood's Law applied to CS101

#15

Post by shoki »

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

Re: Algorithms.js – Atwood's Law applied to CS101

#16

Post by feliperibeiro »

shoki wrote: post #11
feliperibeiro wrote: post #3

Earlier quoted context omitted.

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

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

Re: Algorithms.js – Atwood's Law applied to CS101

#17

Post by akilism »

feliperibeiro wrote: post #10
teh_klev wrote: post #8

Earlier quoted context omitted.

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.

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.

What percentage would you say are clueless about CS101 basic things?

Re: Algorithms.js – Atwood's Law applied to CS101

#19

Post by delluminatus »

akilism wrote: post #17
feliperibeiro wrote: post #10

Earlier quoted context omitted.

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.

What percentage would you say are clueless about CS101 basic things?

I would estimate 75% of Web developers are "clueless" about algorithms and data structures (although that's a fairly strong word).

Re: Algorithms.js – Atwood's Law applied to CS101

#20

Post by TheLoneWolfling »

shoki wrote: post #15

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

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.
Post reply on HN