How do the operations LDA, STA, SUB, ADD, MUL and DIV work in Knuth's machine language MIX?

Question

I have been reading the Art of Computer Programming by Donald Knuth Volume 1. Now I finished the first part where all the mathematics were explained and it was quite a pleasure. Unfortunately, on p. 121 he starts explaining this fictional machine language called MIX based on real machine languages in which he will subsequently explain all the algorithms and Mr. Knuth is losing me completely.

I hope there is someone here that 'speaks' a bit of MIX and can help me understand it. Specifically, he lost me where he starts explaining different operations and showing examples (p. 125 onward).

Knuth uses this "instruction format" with the following form:

He also explains what the different bytes mean:

So the right byte is the operation to be performed (e.g., LDA "load register A"). F byte is a modification of the operation code with field specification (L:R) with 8L + R (e.g., C=8 and F=11 yields "load A register with the (1:3) field). Then +/- AA is the address and I the index specification to modify an address.

Well this makes some sort of sense to me. But then Knuth comes with some examples. The first I do understand except for a few bits, but I cannot wrap my head around the last three of the second example and nothing at all from the more difficult operations in example 3 below.

Here is the first example:

LDA 2000 just loads the full word and we see it completely in register A rA. The second one LDA 2000(1:5) loads everything from the second bit (index 1 ) till the end (index 5) and that is why everything except the plus sign is loaded. And the third with LDA 2000(3:5) just loads everything from the third byte till the last. Also LDA 2000(0:3) (fourth example) kind of makes sense. -803 should be copied and the - is taken and the 80 and 3 are placed at the end.

So far so good, in number5, if we follow the same logic, LDA2000(4:4) it only transferring the fourth byte. Which it indeed did to the last position. But then, in LDA 2000(1:1) only the first byte (the sign) should be copied. This is weird. Why is the first value a + instead of a - (I expected only the - to be copied). and why are the other values all 0 and the last a question mark?

Then he gives the second example with the operation STA (store A):

Again, STA 2000, STA 2000(1:5) and STA 2000(5:5) make sense with the same logic. However, then Knuth does STA 2000(2:2). You would expect to have the second byte copied which equals 7 in register A. However somehow someway we end up with - 1 0 3 4 5. I have been looking at these for hours and have no clue how this, or the two example that follow this one (STA 2000(2:3) and STA 2000(0:1)) can result in the contents of the location as displayed.

I hope someone here can shine his light on these last three.

Furthermore, I also have big trouble with the page where he explains the operations ADD, SUB, MUL, and DIV. The third example, see

This third example is my final goal to understand and right now it makes absolutely zero sense at all. This is very frustrating since I do want to continue with his algorithms but if I don't understand MIX I will not be able to understand the rest!

I hope someone out here has had a course on MIX or sees something that I do not see and is willing to share his or her knowledge and insights!

Answer 1

The design is a child of the 1960s, back when bytes had 6 bits and decimal computing was common. Machines had to compete with 10 digit calculators. It must be emphasized that this is a fictional architecture, actually implementing it will be difficult since a byte doesn't have a fixed size. MIX can work in binary where a byte stores 6 bits, you'd get the equivalent of a 31-bit machine: 1 bit for the sign and 5 x 6 bits for the bytes makes up a word. Or can work in decimal where one byte stores two digits (0..99). That doesn't fit in 6 bits (0..63), emphasizing the fictional part of the design.

It does share another common characteristic of machines back then, memory is only word addressable. Or in other words, you could not address a single byte like you can on all modern processors. So a trick is needed to lift byte values out of a word, that's what the (first:last) modifier does.

Number the parts of the word from 0 to 5, left to right. 0 is the sign bit, 1 is the MSB (most significant byte), 5 is the LSB (least significant byte). The most important detail is that you have to shift the bytes, the last addressed byte in (first:last) becomes the LSB in the destination.

So the simple ones to understand are LDA 2000(0:5), copies everything, LDA 2000(1:5), copies everything except the sign bit, LDA 2000(3:5) copies 3 bytes without any shifting since the LSB is copied. As long as last is 5 then nothing particularly special happens.

LDA 2000(0:0) is easy to understand as well, it only copies the sign bit, none of the bytes.

LDA 2000(0:3) is where the trouble starts. A picture might help:

+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+
  |
  v
+---+---+---+---+---+---+
| 0 | x | x | 1 | 2 | 3 |
+---+---+---+---+---+---+

(0:3) moves the sign bit and bytes #1 through #3. Note how byte #3 becomes the least significant byte in the destination word. It is this shift that probably causes confusion.

Perhaps LDA 2000(4:4) becomes clear now as well. Only a single byte is copied, it becomes the LSB in the destination. Same recipe for LDA 2000(1:1), now moving byte #1 to byte #5.

Answer 2

About the loads and stores: it seems that the sign goes to the sign, if included whereas the rest of the bytes in the field spec go to/from the lowest bytes of the register. The field sped describes the field in memory not in register.

STA 2000(2:2). You would expect to have the second byte copied which equals 7 in register A. However somehow someway we end up with - 1 0 3 4 5.

Here the memory bytes from 2 to 2 (length is 1 byte) is written by the lowest one (length) byte of the register.

Note that the sign is not ordinary "byte", so in loading the field 0 goes to the sign and not the lowest byte, like the other bytes would go to. It might be a good idea to think of field 0 as sign without thinking about its location.

STA 2000(0:1) stores the data in the memory fields 0 and 1: that's sign bit (memory field 0) and the lowest byte from the register to memory field 1.

When it comes to the arithmetics, note that the architecture is not normal byte oriented, but rather kind of digit oriented. The first example (add) looks like it uses decimal mode, or the explanation uses decimal notation. Not sure which.

From the wikipedia (link by "500 - Internal Server Error"):

MIX is a hybrid binary–decimal computer. When programmed in binary, each byte has 6 bits (values range from 0 to 63). In decimal, each byte has 2 decimal digits (values range from 0 to 99). Bytes are grouped into words of five bytes plus a sign. Most programs written for MIX will work in either binary or decimal, so long as they do not try to store a value greater than 63 in a single byte.

Answer 3

Here is another way to make the store operations for Knuth's MIX computer make sense. In a store operation like STA 2000(a:b) the field specification (a:b) does not refer to the bytes in the register, but the bytes in the memory location. It says store the data in rA in memory location 2000 starting at a in 2000 and ending at b in 2000. It then takes only the necessary bytes in rA, starting from the right and stores them in 2000.

So if we have memory location 2000 like this:

- 1 2 3 4 5

and rA looks like this:

+ 6 7 8 9 0

and then we execute STA 2000(2:2) the result is

- 1 0 3 4 5

because the byte at 2 and ending at 2 is replaced in memory with the values in rA starting from the left: 0. STA 2000(3:3) would then leave memory location 2000 like: - 1 2 0 4 5, and STA 2000(4:4) would give us - 1 2 3 0 5.

Similarly, STA 2000(2:4) gives us - 1 8 9 0 5, replacing bytes (2:4) in 2000 with 3 bytes from rA, starting from the right in rA and counting to the left, so 8 9 0 of + 6 7 8 9 0 replaces 2 3 4 of - 1 2 3 4 5.

This wasn't Knuth's clearest moment but if you carefully read his explanation on the page you showed it does make this clear.