People often say "TAOCP is a dense, technical book, you don't just sit down and read it cover to cover." It is dense and it is technical, but it's also a joy to sit down and read and this is why. Knuth doesn't present an algorithm and annotate it with (Foobar 1968) and that's that. He says "Bazquux came up with an early version of this algorithm in 1962 while working on missile trajectories for the Department of Defense, then Foobar came up with the linear-time optimization that we all use today." Stuff like that.
I feel like this is often a distinction between engineering and science books.
I'm used to reading books on physics where the authors (even the Russians) give a bit of background and (usually made up) history but when I go to read a book on something like Finite Element Analysis (For engineers) it feels like the author is literally just dumping his life's work into LaTeX without any thought beyond A->B.
Don't get me started on pages and pages of MATLAB or Fortran code without any indentation, comments or variable names longer than two characters. (This is why I believe writing algorithms in real programming languages is playing with fire in textbooks).
Matlab by itself isn't the problem, it's just that a lot of professors write pretty terrible code in their textbooks. Python won't fix that. None of the mathematics, physics, or engineering texts had much history outside of some occasional excerpts. I'd like to see more of that though as it helps things click for me.
I think MATLAB is a little bit of a problem. Or at least, I want to kill myself whenever I have to use it. Python too although in more subtle ways (I like to abuse the type system, Python is just a hacked together pile of shit with tolerable syntax)
Physics textbooks tend to get "unique" when you get to topics like Quantum Field Theory. Basic Textbooks are usually fairly to the point.
"Advanced Engineering Mathematics" is a good book with a fair amount of history (and written by a mathematician so no Engineering-isms e.g. Notation recognizable to other human beings)
With Matlab, you can immediately create a Matrix and transpose it, find the inverse...etc. I think it is optimized really well for undergraduate excercises that are really simple (I have two numerical methods textbooks which use Matlab fine). I agree that anything more complex than a couple of functions and a loop is probably better off somewhere else in a lot of cases. With that being said, it has built-in support for GUIs, sparse matrices and other stuff which is a lot harder in C++, so easy to see why it is popular for academic and R&D type work. For a student, the commercial cost is only ~$30 or free at a lot of schools, so usually not a barrier.
I literally mentioned Python in one of my above comments lol and it is my daily driver. Still, as an undergrad with zero programming experience, Matlab was very easy to use for the kind of things that undergrads do in engineering and physics (play with matrices, differential equations, make charts...etc). I would agree that machine learning is likely to be easier in Python, but then again, ML students already know how to code, understand OO, and other concepts. Matlab is popular where people are good at math, but have no clue what objects are.
These are issues that a good editing process would resolve. Unfortunately the market for advanced engineering textbooks is so small that it's tough to justify paying an experienced editor to work through multiple revisions.
That's true about physics! I wonder if there are other fields that are written in such casual style. Undergrad textbooks in math are also very dry affairs. David Mackay was an exception, but he is a physicist.
I agree that Knuth's exposition is a joy to read, and there are a lot of significant mathematical insights to be had within those volumes. I just wish he could get away from MIX/MMIX. I don't find it very useful or interesting as a pseudocode, and I think it gets in the way of understanding.
On the contrary, I think it's extremely useful to have the algorithms realized in a form that has a cost model free of handwaving. The books are to a great extent focused on computational costs, and high-level languages obscure those costs.
The only exception is that the books only rarely dive into the variable computational costs due to operating on values of different sizes; heapsort, for example, is only O(N log N) time if comparisons take constant time, while, in fact, as key cardinality approaches infinity, key size grows as O(log N). (Which is why O(N) time sorting is possible.) This kind of thing is growing more important as hardware design becomes more accessible; there are probably more people writing VHDL and Verilog now than were writing any kind of software when Volume 1 came out.
So I think using a high-level language would get in the way of understanding those costs, and even to some extent how to implement the algorithm in other contexts.
If you just want to implement a red-black tree or something, then sure, the MMIX code isn't going to help you. But he also presents all the algorithms in pseudocode, so you can use that.
There's no reason you can't take into account things like varying key size, memory allocation, etc. in your computational model when it matters. For comparison sorting, the reason it isn't done is that if you're comparing keys of the same length, in the worst case, you have to look at the entirety of both keys. O(n log n) might be misleading, but it's a white lie at best.
There are a lot of very interesting issues there. For example, surely you have to look at the entirety of both keys at least once, yes; but you don't have to do it on every comparison, for example in mergesort where you can store a longest common prefix between pairs of adjacent keys and avoid comparing them byte by byte most of the time, or even storing them. The algorithm is tricky both to implement and to analyze, and I don't think anyone has done it, because there are better options for long keys; but I conjecture that it actually gets mergesort down to a real O(N log N) instead of the O(N log N log N) of the usual mergesorts.
I suspect that isn't the reason this kind of analysis isn't usually done, though. If you measure the running time of a standard comparison sorting algorithm on real data on almost any general-purpose computer from 1955 to 1985, you will find that, above very small sizes, it is quite precisely proportional to N log N, where N is the number of records. The extra factor of log N doesn't show up. Why is that?
It's because almost all of those computers, even bit-serial designs like the RCA 1802 and the LGP-30, aren't bit-addressable; the smallest amount of data an instruction can manipulate is a character, typically 6-9 bits, but often 32 bits. And almost none of them could manage more than 4 gigabytes of data, because that would have been too expensive. So in practice the average time to compare two separately stored keys does not vary by a factor of 100 or so over the data sets the machine could process, as you would expect from looking at key unique prefix length. It might vary by a factor of 2 to 4, but more often was actually constant. MIX in particular had 5-character memory words, but only 4000 words of memory, so its comparison time for internal sorting is quite precisely constant for any realistic data.
After 1985, caches and massive parallelism complicate the picture a bit, initially for largish machines (though Stretch too had cache, such monsters were exceptions) and finally for almost all types of computers, though perhaps not yet the numerical majority of computers, which are probably mostly 8051s and Cortex-Ms and things like that.
Anyway, back to the issue at hand: assembly language exposes all the computational costs by default, which is what you want if you're going to prove theorems about them, while high-level languages obscure them by default, so more of your theorems will be incorrect. And that's Knuth's primary concern.
That level of single-minded pursuit of excellence is the reason we can learn things from books Knuth wrote in the 1960s that are still useful for programming computers that are literally a billion times bigger than the machines Knuth used as his model. It's also the reason he's not done yet, 55 years later, with what he thought would be a single book, done in a year or two.
>I conjecture that it actually gets mergesort down to a real O(N log N) instead of the O(N log N log N) of the usual mergesorts.
I don't think it does in the worst case. I'd bet money you could construct an adversarial input that would force you to look at more of each key than you'd have to in order to get down to "real" O(n log n).
>MIX in particular had 5-character memory words, but only 4000 words of memory, so its comparison time for internal sorting is quite precisely constant for any realistic data.
If we're being precise here, then it is certainly bounded above by a constant. But, this is also the same sense in which there is literally no such thing as a Turing machine (all physical machines, even one the size of the universe, are linear bounded automata, at best).
> Anyway, back to the issue at hand: assembly language exposes all the computational costs by default, which is what you want if you're going to prove theorems about them, while high-level languages obscure them by default, so more of your theorems will be incorrect. And that's Knuth's primary concern.
Except, no, you don't. Both you and I just got through explaining why.
> That level of single-minded pursuit of excellence is the reason we can learn things from books Knuth wrote in the 1960s that are still useful for programming computers that are literally a billion times bigger than the machines Knuth used as his model. It's also the reason he's not done yet, 55 years later, with what he thought would be a single book, done in a year or two.
No, it most certainly is not. I'm assuming you've read at least some of TAOCP. Knuth certainly introduced some mathematics and techniques for the analysis of algorithms in TAOCP, but literally none of the algorithms themselves were first published there. This is not a research monograph. It's a reference. The algorithms themselves were published and proven, including runtimes, before they ever made it into those pages.
And, yes, there is plenty that almost anyone can learn from these books and the subsequent fascicles, but it's nothing to do with the computational model. Not one result in TAOCP contradicts the previously published work. We can learn from it because there is simply so much there to learn from. There's a reason that when Steve Jobs told Don Knuth "I've read all your books," Knuth responded that jobs was "full of shit." [0]
Only a very tiny part of the books is in MIX/MMIX (by my count from 3 years ago; details here: https://news.ycombinator.com/item?id=14520230) — if you don't care about it just ignore those programs/sections; it doesn't get in the way of anything. (Similarly you can ignore the mathematics if that's not what you want. You'd be skipping past a big chunk of the book in that case, though.)
On the other hand, MMIX is actually a very nice architecture for a programmer to write assembly/machine code for — it has lots of registers, etc. It's more pleasant to write in MMIXAL than x86 Assembly or (I imagine) ARM or even RISC-V. So if you just want that part of the programmer experience, it's a great way to have some understanding at all levels.
Yeah that’s actually what I found intimidating about TAOCP when I was in undergrad. But I stuck with it, and it was a genuinely good read. I feel like SICP is a better introductory text, though.
MMIX programs can actually be run, and MMIX has multiple simulators. Actual MMIX chips can be made. MMIX also allows students to reason about the properties of modern chips without experiencing quite the complexity they'd have to deal with normally. This is valuable for many reasons.
Yes, that's part of the tradeoff between (what could theoretically be) actual machine code and pseudocode. The other advantage of a language like MMIX is, as another comment stated, you can't ignore things in the cost model. This allows more precise calculations of what the runtime of these algorithms is.
OTOH, pseudocode is easier to understand, partially because you don't have to think about some of those extra things that don't actually matter in the cost model. For an expository text (and, TACOP is an expository text), I think MMIX comes down on the wrong side of the tradeoffs.
