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 books don't seem to be a reference much of the index for major results points to exercises and the content is often comparing two algorithms together. Kirchoff's law of electrical circuit theory is used to analyze program control flow where the number of times an instruction is executed must equal the number of times a program transfers to that instruction. Knuth dislikes jargon and everything is practical you won't find theoretically good on paper algorithms where inputs are jacked up to infinity that hide a huge constant of ops like when Knuth wrote The Stanford GraphBase book and discovered Kruskal's algorithm beats Fibonacci heaps. The algorithms from that book are all in volume 4.

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.

I'm going to crash course some lectures from MIT's 6.004 on RISC-V while reading the TAOCP chapter 1.3.1 on MIX which is a simple 1960s machine.

First is Binary Arithmetic. We're only watching half the lecture but if you wanted to learn about adders that's how modern arrays are indexed in logarithmic time with carry save adders. So when you think about arrays being linear they're actually not it's a tree structure hidden from you by the hardware. Watch this lecture if you don't remember binary encoding or modular arithmetic.

Second is Sequential Circuits. A multiplexer or mutex is a combinational circuit that has n-inputs and based on the select signal it forwards the input to the output or leaves the output in its present state. Remember this. The ALU is all the arithmetic. Now you know feedback really just means a cycle assuming you took graphs in some intro course. D Latch is a mutiplexer, C input is the selector for the D input. If C input is 0 you selected to change the state of Q to D otherwise Q stays the same state as before. An inverter does what you think it does switching inputs from 0 to 1 or 1 to 0. We learn what a clock is, it's a D Latch circuit which can hold state combined with other D Latches in a 'flip flop' combination so that the C input is a periodic signal going up and down and all flip flops are connected to the same C signal or clock. There's some content on time constraints and other levels of detail we don't care about so you can skip this. Then finally the clock time is the upper bound on how long of a delay it takes to propagate all changes in that combinational circuit and again the details don't really matter to us just skim this content. Write enable is dropping another multiplexer in to a flip flop. @32:50 this is what we came here to know. A register is write enabled flip flops which is a bunch of combined multiplexers all with the same clock that initializes the state and can change state. We don't have to watch the rest of the lecture.

Third is Programmable Machines. Skip to Random-Access Memory. That exact same memory diagram is in 1.3.1 (fig 13 the MIX computer). The much simpler MIX arch doesn't use hex to access memory locations it uses 0 - 3999. @7m flip through 1.3.1 as you watch this, Mem[0x100c] in the slides is equivalent to CONTENTS(4108) if MIX had that many memory locations it could address. MIX is a typical von Neumann computer so this is exactly how it works, instructions are fetched from memory and evaluated using the registers to hold state and a 'location counter' (today called program counter) is updated to point to the next instruction in memory to load. The instruction definition wasn't very clear here but is in TAOCP. In figure 3 of 1.3.1 the instruction is 5 bytes, and C field or byte 5 is the opcode to run. F is a range selector, I selects one of the 6 index registers and then adds their contents to the address field before executing the instruction, the remaining two are the address and first field is a sign -/+. Now imagine a stream of these instructions (sign)(address)(modifiers)(opcode) being executed one at a time and a modern desktop/laptop can handle around 100m instructions per second. On a modern system you want to write your program using the principle of locality so when the CPU grabs instructions and holds them in cache that all the next instructions are contained in that grab or else execution has to stop and instructions fetched from slower memory like RAM which is called a cache miss. Volume 4a covers cache strides or hit patterns and cache oblivious algorithms.

Stop second lecture before 18m (where she goes into RISC arch) and let's review chapter 1.3.1 of TAOCP. Bytes weren't the standard 255 when Knuth wrote this however he notes it won't matter since the programs don't depend on byte sizes. One byte in MIX holds 0 - 63 decimal numbers so it's 6 bits or 2⁵ + 2⁴ + 2³ + 2² + 2¹ + 2⁰ or 111 111 = 63 or 010 001 is 17. The word size in MIX is 5 bytes with an actual sign instead of two's complement where the first 0 or 1 is interpreted as pos/neg. This is because MIX is also a decimal computer which is wtf tier but we're in the world of wild compsci and not the conformity of texts from undergrad. The instruction format in figure 3 the 4th or F byte represents 8L + R so (1:3) field select is 8(1) + 3 or 11. The opcode is a number mapped to an operation so if C = 8 that means load into register A and there's a table figure here in this chapter and if you open the back cover you see the same table which lists all opcodes.

MIX has very basic peripherals for input like tape drives but this doesn't matter we use a turing machine tape drive abstraction for some complexity theory still anyway. Consider the 'tape' to be Amazon cloud s3 buckets and you have to remotely read them into memory somehow if you want a modern example. We can come back to this chapter and do all the exercises once we finish the prelims.

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.

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