MIX DIV operator, and Conversion of packed bytes number

Question

I'm working through Knuth's The Art of Computer Programming, and I have a question about the MIX assembly language, particularly the DIV operator.

On page 133, he gives an example of how the DIV operator affects the Accumulator and Extension registers, given a particular state of those registers, and the input memory cell. The question is described (and answered, I think) in this Stack Overflow post: How does division work in MIX?

My problem is that the person who answered converted the value of the 10-byte word stored in rAX (registers A and X) into a single number, using a method that I don't understand:

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)

Can somebody walk me through this conversion?

Thanks, Sam

Answer 1

It depends on the byte size that you're using. Knuth deliberately leaves the underlying implementation of bytes undefined - each byte can support anywhere from 64 to 100 underlying values, but the minimum is 64, and that's what most implementations seem to use.

Let's say each byte holds 64 values, and say you have the following register contents in rA:

+ 01 02 03 04 05

The least significant byte is on the right hand side. Therefore, the "overall" value of the entire rA register would be:

= (1 * 64^4) + (2 * 64^3) + (3 * 64^2) + (4 * 64^1) + (5 * 64^0)
= (1 * 16777216) + (2 * 262144) + (3 * 4096) + (4 * 64) + (5 * 1)
= 17314053

That's exactly what GNU MDK will give you:

MIX> weval 1(1:1),2(2:2),3(3:3),4(4:4),5(5:5)
+ 01 02 03 04 05 (0017314053)

For rAX (rA and rX considered as one register), it's the same idea, except you put rA to the left of rX. So if you have:

rA = + 01 02 03 04 05
rX = + 06 07 08 09 10

The overall value would be:

(1 * 64^9) + (2 * 64^8) + (3 * 64^7) + (4 * 64^6) + (5 * 64^5) +
(6 * 64^4) + (7 * 64^3) + (8 * 64^2) + (9 * 64^1) + (10 * 64^0)

For a decimal implementation, you would just use 100 instead of 64 as the base. So in the initial example, you would end up with:

= (1 * 100^4) + (2 * 100^3) + (3 * 100^2) + (4 * 100^1) + (5 * 100^0)
= 102030405

Hope that helps.