CODEWITHSUNDEEP
divisionknuth
Rich006
Rich006

Reputation: 215

Knuth MIX division example

I was having trouble following an example in The Art of Computer Programming, (3rd Ed.) by Donald Knuth. I figured it out by starting to ask here ("explain it to a duck"), so I thought I might as well leave my "question" here in case it might help someone else.

Knuth gives an example of the DIV operator in his (made up) MIX machine. In this machine a byte may be either 6 bits (max value 63) or 2 digits (max value 99). A word consists of a (+/-) sign followed by 5 bytes. The instruction DIV 1000 takes the sign and the 5 bytes from register A (rA) and the 5 bytes from register X (rX), combines them into a 10-byte number, and divides by the contents of location 1000. The whole part of the quotient is put into rA, and the remainder is put into rX. The sign of rA is set to the sign of the quotient, and the sign of rX is set to the previous sign of rA. The simple example in the book is:

DIV 1000
+---+---+---+---+---+---+
| + |                 0 |  rA before
+---+---+---+---+---+---+
| ? |                17 |  rX before
+---+---+---+---+---+---+
| + |                 3 |  Cell 1000
+---+---+---+---+---+---+
| + |                 5 |  rA after
+---+---+---+---+---+---+
| + |                 2 |  rX after
+---+---+---+---+---+---+

In this example, each set of 5 bytes represents a single number. The dividend is 0+17 = 17, the divisor is 3, and the quotient is 5 remainder 2. So far so good. Note that it doesn't matter if the machine is binary or decimal, because the values are unambiguous. (The question mark indicates that the initial sign of rX doesn't affect the result.)

Where it gets tricky is if not all of the bytes in rA or rX are used to represent a single number; in that case the number base can affect the result, meaning the result is ambiguous. The next example in the book is

DIV 1000
+---+---+---+---+---+---+
| - |                 0 |  rA before
+---+---+---+---+---+---+
| + | 1235  | 0 | 3 | 1 |  rX before
+---+---+---+---+---+---+
| - | 0 | 0 | 0 | 2 | 0 |  Cell 1000
+---+---+---+---+---+---+
| + | 0 |  617  | ? | ? |  rA after
+---+---+---+---+---+---+
| - | 0 | 0 | 0 | ? | 1 |  rX after
+---+---+---+---+---+---+

Here bytes 2 and 3 of rX represent one number, but the other bytes represent separate numbers. The question marks in the "after" lines indicate that the binary and decimal machines will give different results.

Why is the 617 unambiguous, but other values are ambiguous?

Upvotes: 0

Views: 20

Answers (1)

Rich006
Rich006

Reputation: 215

If the machine is decimal, the bytes of rX represent 1235(100^3) + 3(100) + 1 = 1,235,000,301, and the divisor is 2(100) + 0 = 200. The quotient is then 6,175,001 remainder 101, and so the digital bytes of rA become 6 17 50 01.

But if the machine is binary, the bytes of rX represent 1235(64^3) + 3(64) + 1 = 323,748,033, and the divisor is 2(64) + 0 = 128. The quotient is 2529281 remainder 13, which can be written 9(64^3) + 41(64^2) + 32(64) + 1, and so the binary bytes of rA become 9 41 32 1. But 9(64) + 41 = 617, so bytes 2 and 3 can be interpreted as 617 regardless of whether the machine is decimal or binary. However, the less significant bytes are different.

Similarly, the last byte of rX is 1 for the decimal and binary calculations: the remainder is 1(100) + 1 in the decimal calculation, or 1 in the binary calculation. Either way, the least significant byte is 1. So the 617 in bytes 2-3 of rA, and the 1 in byte 5 of rX, are the same regardless, but all the other bytes are different, hence the question marks in all other byte slots.

Upvotes: 0

Related Questions