Let's Read the Art of Computer Programming

See the book site for details or where to get official pdf/copies. I'm using the 3rd edition look for the most recent printings that fix errata. If you can't buy them use Library Genesis to get a pdf.

Everybody talks about the famous old quote in the back of volume 1 by Gates: 'you should definitely send me a resume if you can read the whole thing'. I found a more recent quote from 2005:

BILL GATES: ..say somebody came for an interview and they said "Hey, I read the Art of Computer Programming, that’s all I ever read, I did all the problems", I would hire them right then.

MARIA KLAWE: You’d hire them right then?

BILL GATES: Yeah, that’s right.

MARIA KLAWE: So would I.

BILL GATES: Even if they didn’t do the double-star problems, I mean, just the fact that they’d read the whole book, you know, those are the kinds of things you need to know to be a good programmer. Actually, there’s some of that you don’t even need to know, but the kind of algorithmic thinking that’s promoted there." (2005 interview with then Princeton Dean of Science).

I'm not sure what the double-star problems are maybe the earlier editions had this labelling scheme. I also don't think the people who run HR at bigtech have ever heard of these books so I wouldn't read these and expect a job in 2024.

Volumes 1-3 still contain the original MIX machine and there exists GNU MDK or other software to run MIXware meaning compile .mixal files to .mix and simulate running them either with mixvm, gmixvm GUI, or a scheme interpreter.

There exists the MMIX Supplement by Martin Ruckert to replace the 1960s MIX architecture with MMIX (RISC) in volumes 1-3 which Knuth has announced on his book site he plans to someday replace. MMIX arch you can customize the hardware however you want using Knuth's 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, bus speeds, then test running various algorithms on that custom config. He documented that program with the book MMIXware: A RISC Computer for the Third Millennium and all the code is written in literate programming style so you can read the programs like you would any other book. MMIX software there is mixmasters version or the 2017 sealed in time Knuth version you compile from c-web sources that are extensively documented.

Knuth releases these updates called fascicles as drop in replacements for chapters and there's an MMIX replacement for most of 1.3.x but since the first 3 books have so much MIXAL content and I carry them around to read I'll switch to MMIX whenever we reach volume 4.

A reason to learn this material is given by DJ Bernstein's talk a few years ago about the death of optimizing compilers, see these slides where at the end Knuth describes how hand coded assembly will always be faster than the best optimizing compilers.

The comparison instruction wants a 7 char password, the 'create password' sub-routine generates a 7 char password, try it just entering the 7 hex numbers in one password string, success.

Set breakpoint at most interesting function which looks like check password. Enter 'test' as text for password, then c to zip to the breakpoint. Pressing s and stepping, r15 is pointing to 439c where we see 7465 7374 or 'test'. Notice the instructions however:

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)

It's comparing each byte in the memory that r15 points to some constant hex values by offsetting 2 bytes each time. They are in little endian format, #0x5d2b is represented as 2b5d in the instruction, #0x2170 is 7021 etc., so take all the comparison instructions and enter the password as little endian format and success, operatives inside again.

Note the actual code/instruction the machine uses is bf902b5d0000 or bf9070210200 if you read the 'LockIT Pro' manual the opcode is cmp (compare) source, destination which is for our visual benefit only in the debugger and for writing assembly so even with machine code there is some syntax abstraction.

Passwords must be between 8-16 chars so I entered a gigantic password and while stepping through the execution noticed it overflowed to the second memory location 2410. Ctrl-f the instructions for 2410 and there's a comparison there so I overflowed the hex password to 17 digits with that comparison at 2410.

Entered another gigantic password, noticed it overflowed to where the program counter (the next instruction) is so overflowed it to change the pc to 'unlock door' instruction in little endian format.

We can't see all the disassembly and have to step watching 'Current Instruction' box. Enter a single character password as a test and step until you see a cmp for the address in r4 offset by -0x24 or 36. Move back that amount in memory and you're at the password you just entered, so enter (little endian) whatever the cmp constant is.

They took away the function to unlock the door, we have to read the manual about how the HSM 2 model works. In 3.1 This enables the CPU to trigger software interrupt 0x7F to directly trigger the door lock to unlock so we want to bamboozle this code to somehow run 0x7F. As usual start with a gigantic password and see where it is stored. Mine begins at memory location 347c. Looking at the conditional unlock door function I want to push 0x7f the unlock command instead of 0x7e the password comparison command, and then call that interrupt after.

If you overflow your password you'll see in the 'current instruction' box it will run whatever we put there, so try the instructions 30127f00b0123245 which in line 445c we see pushes the door unlock code to the stack and calls an interrupt to pop the stack which will signal to open the door.

Two new functions strcpy and memset. Memset appears to clear the password storage memory and strcpy removes all null bytes 00 out of our password entry so if we want to use 0x7f or 7f00 we have to steal some code to add/subtract or AND off some bits to avoid strcpy deleting our payload. I used 32 junk filler + 0244 + payload as a hex password after many trial and error getting the overflow to lineup after strcpy killed my 0044 address.

You can play with instructions here and use any hex calculator. I added some arbitrary value to 0x7f, moved it to a register, pushed it to the stack and called that interrupt again. Success. We achieved enough of the programming prereqs.

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 hundreds of problems in TAOCP we really only need a single variable crash course that focuses on engineering instead of abstract real analysis.

There is a global survey of calculus education here the biggest problem students have is understanding that limits are an infinite process. It's so bad that in 2016 Arizona State profs were paid by the NSF to redo the curriculum so they came up with one that doesn't have limits at all called Project DIRACC it only contains the natural idea of a limit via exhaustive Archimedes style approximation (that doesn't end ergo infinite process) when accumulation (integration) is studied. They recommend Peter Lax's treatment of limits so that's what we'll do.

• Obtain the book Calculus with Applications by Peter Lax/Terrell on library genesis. The errata for it is here.
• Obtain Evan Chen's Napkin it's a crash course in metric spaces and topology both which will help us better see what is actually going on.
• Obtain the free book The Calculus Integral by Brain S Thomson it's kind of a radical theory of integration book that can be used to really understand what continuity actually is.

Limits are an algebra of inequalities so we start right away with inequalities. Eq (1.1) \(\epsilon\) is epsilon a variable traditionally used for something close to zero or in other words a very small displacement and is explained in chapter 1.3. Problem 1.8 we can solve right now it states for any numbers a and b, only one of those 3 conditions hold in b <= a <= b and since b can't be less than itself it must equal a. Figure 1.9 multiply each side by 1/4 and square root both sides. In the visual proof it's the side of a plus the short side of b squared or the area of a square which is side x side.

Search YouTube for any triangle inequality demonstration.

Example 1.6 we want to prove any square with the same perimeter as a rectangle has a larger area. The perimeter of 11x1 rectangle is 2(11+1) = 24 and a square having the same perimeter would be (11+1)/2 or 6 each side = 24. Write this as the A-G inequality then square both sides to get rid of the square root and magically we have a proof that the area of any rectangle (Width x Length) is smaller than a square of same perimeter.

The proof for n = 4 in Eq (1.2) if a = mean and b = mean then sqrt(ab) <= (a + b)/2 and substitute back in the values for a and b.

Problems Many of these are good and teach rewriting inequalities.

Ex 1.7 I think derived by:

• \((\sqrt x - \sqrt y)(\sqrt x + \sqrt y) = x - y\)
• \((\sqrt x - \sqrt y) = \frac{1}{(\sqrt x + \sqrt y)} \cdot x - y\)
• \(\frac{1}{(\sqrt x + \sqrt y)} \cdot (x - y) \le \frac{1}{4} \cdot (x - y)\)
• \(\frac{1}{(\sqrt x + \sqrt y)} \le \frac{1}{4}\)

Ex 1.12 is the triangle inequality chapter or example 1.5 in the book.

Ex 1.13 (b) if you add some indexing it's more clear:

• \(1_1 + 1_2 + 1_3 ... 1_{n-1} + x\) = n amount of total terms including x hence (x + n - 1)/n.

Ex 1.14(c) we can see it's less here using a desmos graph. A possible strategy notice if you take the geometrical mean of AH it equals G then the arithmetical mean of A + H will be greater. Ex (d) seems to be asking \(\frac{1}{2} \cdot \frac{2}{\frac{1}{R_1} + \frac{1}{R_2}}\)

Ex 1.16(b) The solution on pg 476 is right under the distributed triangle inequality |a||b-b₀| or 10(0.001) if it doesn't make sense right away.

Ex 1.15 If a value has an exponent n and you take the n-th root you get the same value back again like \(\sqrt[3]{2^{3}}\) = 2 or \(\sqrt[n]{n^{n}}\) = n

Ex 1.17 I tried this but doesn't seem correct:

• 4m = (a + b + c + m)
• 4m + 4m = (a + b + c + m) + (d + e + f + m)
• 2m = h + g
• 2m + 4m + 4m = (a + b + c + m) + (d + e + f + m) + g + h
• (abcdefghmm)^1/10 <= m
• (abcdefghmm) <= m¹⁰
• (abcdefgh) <= m⁸ then 8th root both sides

(b) (abcdemmm) <= m⁸ or (abcde) <= m⁵ and for the general case both times we increased m to show n like n+1 to show n in the book.

Ex 1.18 For (c) if you expand the definition of p(x) where it's a sum of squares into (ax + b)(ax + b) or a sum of multiple polynomials like a²x² + 2abx + b² then you can group all ax terms so you have (a₁² + a₂² + …)x or (P)x, group 2abx so you have 2(ab₁ + ab₂ + …)x or 2(Q)x etc. Then square root both sides of Q² <= PR and you get the Cauchy-Schwarz inequality. A full explanation of (b) is in the book The Cauchy-Schwarz Master Class by J. Michael Steele. There is entire books written about manipulating and proving inequalities because they provide upper bounds for sums with real numbers.

Intervals are again talked about here because that's what calculus is a linear approximation using small intervals. If you look at a curved function and super zoom a point on the curve it appears to be a straight line because locally everything is linear if you choose a small enough interval. That line that appears to be straight is the tangent as we'll soon learn.

Lax defined a set S where every element squared is strictly less than 5.1 but because we are dealing with infinite sets with infinite decimal precision 5.099999… there will always be some finer approximation of decimals who's square is less than 5.1 so the least upper bound is the limit or 5.1

The rounding exercises here I skipped because the entire second half of Vol 2 of TAOCP is all about rounding/floating point and trying to represent real numbers in computers. This is an ongoing problem in AI research trying to build efficient numerical libraries.

The Greek letter epsilon is finally defined. A sequence is a data-structure (a list) containing ordered elements that here are approximations to a number. For example the square root of 2 you can pretend is an algorithm attached to the real line producing an infinite stream of approximations that are stored in a list. This list has the properties that each new entry converges towards the number n who's square is 2 because every additional approximation creates a smaller epsilon or tolerance level between the last approximation. You index and operate on lists the same as programming recursively indexing earlier or inductively indexing future entries. The notation N \(\ge\) n if you watch this starting at 5:30 he draws a geometric intuition of what the limit definition is.

Example 1.11 5n + 5 is 5(n + 1) and now the denominator cancels if you're skimming this chapter.

The approximation of root 2 in 1.3a look at end chapter problem 1.28. If \(s_{n+1} \lt \frac{1}{2} \cdot s_n\) holds for each n then \(s_{n+1} \lt \frac{1}{2^{n}} \cdot s_1\) why is this true? Lax says to repeatedly apply this to the sequence:

• \(s_{n+1} \lt \frac{1}{2} \cdot s_n\)
• \(s_{n+1} \lt \frac{1}{2}(\frac{1}{2} \cdot s_{n - 1})\)
• \(s_{n+1} \lt \frac{1}{2}(\frac{1}{2}(\frac{1}{2} \cdot s_{n - 2}))\) …

Theorem 1.9 is another proof where Lax looks at every digit and since this is an increasing sequence that is bounded eventually there is some index k where all the integer parts of the decimal are the same and all the decimal parts after this index k differ from the actual limit a by 10^-k precision.

Theorem 1.10 another square root existence proof, subtract s² from both sides.

Theorem 1.11 so far proofs in this book are deceptively simple but you have to read them a few times to see how he sets it up often taking two similar sequences with similar limits and comparing them or producing the n+1 sequence term then manipulating the equality to end up in the form of a known limit we can use.

Example 1.19 divide the denominator 2n + 1 by the numerator n: \(\frac{1}{2 + \frac{1}{n}}\) and we already know from Example 1.8 the limit of 1/n is 0 so this limit is 1/2. The necessary conditions for convergence in Theorem 1.12 was the series had to have a limit of 0 so this is divergent.

Theorem 1.13 proof take the entire series and multiply it by (1 - x), you then have 1 minus the successor. To get back to s_n divide the successor by the factor (1 - x). The rest of this chapter is a bunch of examples of series with and without absolute values that partially converge and the ratio test where you ratio the successor in a series and itself.

Problems

Ex 1.25 hah, find all the definitions and theorems in this chapter and illustrate each with an example.

.. cont TODO