5 ms·
It's not easy to make such a comprehensive list over such a broad category, so cheers to the author for trying. I think it's a good list, but to challenge mysel
by Clubber 10y ago
It's not easy to make such a comprehensive list over such a broad category, so cheers to the author for trying. I think it's a good list, but to challenge myself, I tried to think of some things that he missed.
1. Encryption
2. Compression
These might fit into another broad category like OS or Networking, but they are both distinct from those I believe.
- speeder 10y agoIf you read the footnotes he states that he was tempted to include those, but then there would be problematic to separate what algorithms would fit his text, so he decided against including any.
- Cyph0n 10y agoEncryption: RSA Compression: JPEG or MP3
- dom0 10y ago> RSA No thanks.
- Cyph0n 10y agoWhy? RSA is one of the greatest breakthroughs of the last half century in my opinion. It was the first implementation of an asymmetric crypto scheme. Merkle came up with the idea of public key cryptography, but he never provided a mathematical technique to achieve that. Imagine a world where RSA was never invented. We would not be able to exchange secrets over an insecure channel, so naturally, HTTPS/TLS would never have existed - this alone is huge. We would not be able to exchange secure email in a scalable way (PGP). We not be able to securely sign messages for authentication. And there's a ton more. This is without counting the schemes and techniques designed on top of RSA!
- Ar-Curunir 10y agoThere exist other asymmetric encryption schemes; indeed there exists one that is basically non interactive Diffie Hellman key exchange, and DH was discovered before RSA was.
- Cyph0n 10y agoI was under the impression that RSA was first, but I guess I was wrong. DH is a key exchange algorithm, not a general public-key encryption algorithm. So, as far as I understand, TLS would work, but the others I listed would not.
- Ar-Curunir 10y agoRSA was the first PKE scheme, but El Gamal, another PKE, is essentially a small modification of DH. Elgamal was discovered in 1985; before encryption really hit the mainstream.
- Cyph0n 10y agoI see. I'm not too familiar with crypto, so thanks for explaining. I guess that the argument is now: would ElGamal have been invented had RSA never existed?
- Ar-Curunir 10y agoI think so; as I said it's essentially a small modification to DH.
- deleted 10y ago[deleted]
- Cyph0n 10y agoOh, and the FFT should have been included in the article as well.
- Clubber 10y agoSomething just occurred to me; encryption predates software so it's not a software innovation in and of itself.
- VLM 10y agoHow about the very concept of having paradigms of programming (not the specific paradigms like OO or functional, but the idea that you can create a little Turing complete utopia and live inside that utopia never coming out, and, crazily, it actually works in multiple parallel universes of separate paradigms!) Data structures. Including Codd Normal form or maybe Codd is important enough to mention. Sort of a very large scale GIGO. Or maybe the more important aspect of data structures or structured data or Codd is GIGO itself as a debugging concept. The idea of the importance of the algorithm, that its not merely an mathematical amusement that there are different ways to calculate something, but now its of critical financial importance how efficient an algo is in time or space or power ... or patents. Binary. What stopped man from flying until last century was millennia of trying to copy birds and the assumption that failure implied inaccurate copying of birds. What stopped man from computing in the 1600s, 1700s, 1800s was a fierce dedication to building computation hardware out of decimal. Once we gave up on birds and decimal, like a decade later we're flying and computing like crazy. Henry Ford didn't build a mechanical oil burning robotic horse, cool as that would have been, he built a better horse by building a horseless carriage that revolutionized the world for better or worse. Sometimes the most important breakthru is deciding what to give up on. Virtual memory was kinda influential. So.. adders and lookups are so fast and the advantages are so huge that its worth sticking a MMU in the way of address lines... would not have guessed from first principles... Automata theory is kinda important as a theory of computation, like "can you even do it". Imaginary property or intellectual property or whatever you want to call it. The concept of legally owning an integer. The concept of owning a piece of media but not the license to apply whats stored on it. Business method patents along the lines of "... on the internet". Patented data formats that are separate from the copyright of the data stored in the patented form. Copyleft. FOSS. GPL and its less free competitors BSD and others. Domain squatting. Blockchain financial instruments, or properties or currencies or whatever they are. For better or worse imaginary property has driven a lot of "innovation" and "economic activity", some of it even useful.
- Clubber 10y agoThese are all important things but either fall under one of the broad categories or isn't a software innovation: Paradigms of programming, data structures, importance of the algorithm : Falls under programming although I'm not sure why GC wouldn't fall under that as well. Codd : programming (data structures) and transactions. He explicitly references databases in the transaction section. Binary: A hardware innovation. Virtual memory: Falls under OS. Automata: Falls under hardware or programming and possibly sculpture? IP: Falls under copyright / patent law. An aside: I've always known GIGO to stand for Garbage In, Garbage Out.