How does division work in MIX?

Question

Can someone explain to me how division in MIX (from TAOCP by Knuth) works on a byte-to-byte basis?

rA = |-| . . . .0| 

rX = |+|1235|0|3|1|

The memory location 1000 contains |-|0|0|0|2|0|.

When you execute the operation

DIV 1000

the registers become

rA = |+|0|617|?|?|

rX = |-|0|0|0|?|1|

Now I understand the signs on rA and rX, but in what order are the bytes of rAX filled and which divisions are done?

If DIV 1000 leads to every bit divided by 2, then I would expect

rAX = |+|617|0|1|0|-|0|1|0|1|1| 

in which rA contains the division results and rX the remainders (filled from the right side).

I'm probaly missing something here, and Knuth seems to think I should be able to figure it out myself (hence the level 10 questions about it, which I also don't get), but could someone help me out here?

Kati

Answer 1

So I kind of figured it out myself.

If you do the division by hand, by converting the bytes into a single number you will get -210,501,825 (if you're using the smallest kind of byte - which is 6 bits (!) in Knuths book). Divide this by -128, which is the value in location 1000 using the same bytesize.

The quotient is 1644545, the remainder 65, the sign will be postive since both numbers are negative. If you store 1644545 in rA and 65 in rX, you will get

|+|0|6|17|32|01|
|-|0|0|0|1|1|

using the smallest bytesize (which holds 64 numbers). Since Knuth never assumes a particular bytesize in his examples, rX has a number of question marks. The sign of rX is always the previous sign of rA.

Edit: I used the very handy MixEmul utilty to play around with the registers of MIX. This is a pretty nice MIX implementation done in .NET

Kati

Thanks @Ruben Steins. I also have a question about DIV but it's regarding this sentence: "If V=0 or if the quotient is more than five bytes in magnitude (this is equivalent to the condition that |rA| ≥ |V|)..." (towards the bottom of pg. 131. 3rd edition). Would you know what is meant by the bit in bold? How is the condition |rA| ≥ |V| equivalent to saying if V=0 or if the quotient is more than five bytes in magnitude? – Gybe