Let's Read the Art of Computer Programming

I'm going to start with Volume 1: Fundamental Algorithms 3rd edition by Don Knuth and keep going. These are now the most relevant computer science books as industry has shifted to creating their own custom hardware and software stacks. Data is now so massive we can no longer move it around to be computed and the state-of-the-art architecture these days perform computation at the data. Knuth's MMIX (RISC architecture) he created for these books has a free meta-simulator program which is a test bed to try out different chip configurations. You can change instruction throughput, pipeline configurations, branch prediction, cache sizes and associativity, then test running various algorithms on a custom config. This is exactly what you do when writing a prototype FPGA you plan to later manufacturer into a chip.

The physical book itself is a representation of the careful work that has gone into it's writing with high quality typography, paper, and a binding where no matter what page you flip to the book stays flat. If you were to ever buy a physical book this would be one of those books. The pdf version Knuth paid the Berkeley Mathematical Sciences Publishers to create a compressed searchable text with hyperlinks throughout the document and even guaranteed that the final version was correct in all notation/figures. He tells readers to avoid any kind of other ebook format like Kindle where the notation is trashed.

The preface says we should familiar enough with programming that we've written and tested a few programs, which means assembly/machine language programs. I assume you already know basic programming from somewhere else but not an assembly language. We can learn that doing microcorruption.com CTF and having a visual interface to step through all the code in the debugger to see what it does, see how registers are manipulated etc.

Starting the tutorial on microcorruption. At 18/74 in the tutorial all values are in base 16 or hexadecimal. There's many online tutorials to convert or look at a binary to hex table and memorize A (10) and F (15) then the rest are easy. 0x(hex) examples: 0x2 is 2 or 2¹, 0x20 is 32 or 2⁵, 0x200 is 512 or 2⁹. If you forgot how binary works watch this.

At 35/74 in the tutorial this is how you read the memory dump:

      0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
4390: 52 45 02 00 9c 43 64 00 82 44 50 44 74 65 73 74

4390 points to 52, 439c points to 74, if you look in the register state box sp (stack pointer) points to 439a or 50. These are 1 byte each in size or 8 bits. At 44/74 in the tutorial if you move back -0x8 or 8 bytes, count back 8 times or each row of 4 hex values has 2 bytes, so move back 4 rows. If you see 0x2(r15) that means whatever the memory r15 points to, skip 2 bytes. You'll pick it up as we step through the code, and we will step through a lot of code.

There's a manual for the fake lock we are breaking too.

448a:  bf90 2b5d 0000   cmp 0x5d2b, 0x0(r15)
4492:  bf90 7021 0200   cmp #0x2170, 0x2(r15)
449a:  bf90 3256 0400   cmp #0x5632, 0x4(r15)
44a4:  bf90 5467 0600   cmp #0x6754, 0x6(r15)

Onur Mutlu at ETH Zurich every year publishes free and open courses on computer architecture which covers state of the art techniques, hardware security and future architecture like RISC-V. We can view these as we work through the MMIX chapter.

The undergrad course is Digital Design & Computer Architecture w/YouTube playlist here and it's pretty much essential casual viewing to understand how MMIX works. There's no physics or math background needed. These are live streamed lectures so contain breaks and aren't as long as the running time suggests. The graduate course is Computer Architecture and the labs are exactly what MMIXware is: building a cache timing simulator where you can experiment with block size, associativity, change replacement policies, etc.

In the preface 'a knowledge of basic calculus will suffice' is stated however basic calculus to Knuth probably means something like the following. Go to this jstor archive of an interview with Knuth and copy the DOI into Sci-Hub to read the pdf:

At Case, I spent hours and hours studying the mathematics book we used -Calculus and Analytic Geometry by Thomas- and I worked every supplementary problem in the book. We were assigned only the even-numbered problems, but I did every single one together with the extras in the back of the book because I felt so scared (of failing). I thought I should do all of them. I found at first that it was very slow going, and I worked late at night to do it. I think the only reason I did this was because I was worried about passing. But then I found out that after a few months I could do all of the problems in the same amount of time that it took the other kids to do just the odd-numbered ones. I had learned enough about problem solving by that time that I could gain speed, so it turned out to be very lucky that I crashed into it real hard at the beginning.

The second part of the interview:

We should teach people things with an emphasis on how they were discovered. I've always told my students to try to do the same when reading technical materials; that is, don't turn the page until you have thought a while about what's probably going to be on the next page, because then you will be able to read faster when you do turn the page. Before you see how to solve the problem, think about it. How would you solve it? Why do you want to solve the problem? All these questions should be asked before you read the solution. Nine times out of ten you won't solve it yourself, but you'll be ready to better appreciate the solutions and you'll learn a lot more about the process of developing mathematics as you go. I think that's why I got stuck in Chapter One all of the time when reading textbooks in college. I always liked the idea of "why?" Why is it that way? How did anybody ever think of that from the very beginning? Everyone should continue asking these questions. It enhances your ability to absorb. You can reconstruct so much of mathematics from a small part when you know how the parts are put together. We teach students to derive things in geometry, but a lot of times the exercises test if they know the theorem, not the proof. To do well in mathematics, you should learn methods and not results. And you should learn how the methods were invented.

You can see the exact version Knuth used on archive.org the 1950s version w/supplementary problems all in the back but the 1960s 3rd edition has the same content the publisher moved the supplementary problems to the end of each chapter labelled 'misc problems'. There's a version on libgen (95MB size because HD scanned). Herb Gross lectures from MIT OCW that cover the same book are Single Variable Calculus, Multivariable Calculus, Complex Variables, Differential Eq, Linear Alg.

Thomas' book is 900+ pages and took Knuth a year to complete with lectures and teaching assistants while he was at Case Tech. Since we are already doing countless problems in TAOCP including writing our own derivatives program in volume 1 we can begin with a crash course and pick it up later when needed.

Whenever Knuth cites a reference/paper you can use Sci-Hub to get a copy.

The 'quadruple' definition of what an algorithm is will make sense when you try it yourself by hand. First we have f, which defines the computational steps:

• f(n) = n (return the result and terminate, we aren't calling another function)
• f(m,n) maps to f(m,n,0,1), the zero being just a placeholder to enter to the next step.
• Step 1: f(m,n,r,1) maps to f(m,n, remainder of m divided by n, 2)
• Step 2: f(m,n,r,2) maps to f(n) if the remainder is zero, or f(m,n,r,3) otherwise.
• Step 3: f(m,n,p,3) maps to f(n, p, p, 1) swapping m with n, and setting the remainder p to n. The variable p is introduced here to make it explicit that p does not equal zero, as r can be equal to zero so different notation is used but it's just remainder with a new variable.

Let's try it using Knuth's example of m = 119 and n = 544 since the preface told us to try all these algorithms by hand.

f(119, 544)  -> f(119, 544, 0 ,1)
f(119, 544, 0, 1) -> f(119, 544, 119, 2) :divide m by n
f(119, 544, 119, 2) -> r is not 0 -> f(119, 544, 119, 3)
f(119, 544, 119, 3) -> f(544, 119, 119, 1) :set m <- n <- r
f(544, 119, 119, 1) -> f(544, 119, 68, 2) :r = 68
f(544, 119, 68, 2) -> r is not 0 -> f(544, 119, 68, 3)
f(544, 119, 68, 3) -> f(119, 68, 68, 1)
f(119, 68, 68, 1) -> f(119, 68, 51, 2) :r = 51
f(119, 68, 51, 2) -> r is not 0 -> f(119, 68, 51, 3)
f(119, 68, 51, 3) -> f(68, 51, 51, 1)
f(68, 51, 51, 1) -> f(68, 51, 17, 2) :r = 17
f(68, 51, 17, 2) -> r is not 0 -> f(68, 51, 17, 3)
f(68, 51, 17, 3) -> f(51, 17, 17, 1)
f(51, 17, 17, 1) -> f(51, 17, 0, 2)
f(51, 17, 0, 2) -> r = 0 -> f(17) 
f(17) -> 17

The last Markov algorithm example is pattern matching on strings. Alpha \(\alpha\) can be the empty string too so what's happening here is we are replacing characters out of strings every loop according to a set of matching rules exampled here. A is a set of finite alphabet characters, and A* is all the possible strings you could make using ordered sequences of characters from A. Next he defines (sigma, j) where sigma is some string in A* and j is a number less than N which is the final state. So input = (string, 0) and output = (string, num) or a termination state.

From this example we have 3 rules, and if the string doesn't match any rule patterns we terminate the algorithm. The set 'I' is the input so f("101", 0). Omega would be the output f("|||||", 8). Both of these are contained in Q and every other intermediary state like f("0|01", 1).

TODO

---

Home