Hacker Neue

Preferences
Edootjuh parent
What do you mean by that, exactly? Just out of curiosity.
praptak
Many results about unfeasibility of computer-based solutions to some problems were not known. For example the first important results about NP-hardness come from the seventies.

I believe it wasn't even clear that the big O complexity is important in assessing how effective an algorithm is. This is pretty much obvious to us now (sometimes too obvious - there are some edge cases when the constant factor wins over the asymptotic complexity).

scott_s
I agree with everything you said, except the parenthetical. I have difficulty considering matrix multiplication an "edge case," and I think that it's more common than you imply for us to choose algorithms with a higher asymptotic bound because of constant factors and architectural effects (mostly caching).
praptak
Ok, agreed about matrix multiplication and probably a few other problems, disagreeing about cache.

You cannot really say that cache-aware algorithms have higher asymptotic bound. Some of them might happen to have below-optimal asymptotic bound in a cache-unaware memory model, which sort of misses the point of the algorithms being aware of cache.

scott_s
You cannot really say that cache-aware algorithms have higher asymptotic bound.

Don't worry, I'm not. I'm saying that sometimes, naive algorithms have better cache behavior than more complicated algorithms with lower asymptotic bounds.

michaelochurch
Not grandparent post.

I think that one of the differences is that, in 1954, computer programs were single entities written by one person or by a team working closely together. So the "between two pieces of working code" bugs-- which tend to be the nastiest kind in modern development-- weren't really seen yet. Million-line codebases weren't even on the table as a reasonable concept, and the idea of a program depending on 120 other libraries or frameworks was unimaginable.

scott_s
I agree with everything above, but I would like to sum it up in my own words: we (as a species) were so new at writing software, that we had no idea of its inherent complexities. Programming was an after-thought for those that designed the first computers.
Zaak
As soon as we started programming, we found to our surprise that it wasn't as easy to get programs right as we had thought. Debugging had to be discovered. I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs.

— Maurice Wilkes

This item has no comments currently.