2

I seem to recall once reading in one of the tAOCP fascicles Knuth's discussion of calculating the integer quotient and remainder. My memory is that he claims it is not possible to calculate one without the other, and that he believed the results should both be made available to the programmer. The problem being that most programming languages force the programmer to calculate something like q = a/b then r = a%b, but under the hood the CPUB did the same calculation twice, which is a waste.

I've just searched in MMIX Volume Fascicle 1 at the description of DIV in section 1.3.1, but I don't find the discussion I seem to recall.

Can someone tell me whether they recall a similar discussion, and where I might find it?

Jim Newton
  • 594
  • 3
  • 16
  • Are you sure you read it in one of the fascicles (or TAOCP itself), and not in say, some interview or some other paper / book? – ShreevatsaR Feb 26 '19 at 18:30
  • No, i'm not sure. I read the MMIX book about 15 years ago. could very well be my memory is wrong. Just hoping someone else remembered the same thing as me. – Jim Newton Feb 28 '19 at 11:18

1 Answers1

1

The following may be what you're looking for — it's the only relevant mention I found in all the volumes of TAOCP and (pre)fascicles released so far. (It's just a part of a sentence and not an elaborate discussion, but memory can be tricky.) From Volume 1 Fascicle 1, section 1.3′ (MMIX), specifically 1.3.1´ (Description of MMIX). As you know, under “Arithmetic Operations”, the DIV operation is defined such that DIV $X,$Y,$Z (if $Z does not contain zero) sets $X to contain the (floor) quotient of the values in $Y and $Z, and simultaneously sets the rR register to hold the remainder.

Later, under “MMIX versus reality”, the second point is:

Commercial machines are usually deficient in their support of integer arithmetic. For example, they almost never produce the true quotient ⌊x/y⌋ and true remainder x mod y when x is negative or y is negative; they often throw away the upper half of a product. They don’t treat left and right shifts as strict equivalents of multiplication and division by powers of 2. Sometimes they do not implement division in hardware at all; and when they do handle division, they usually assume that the upper half of the 128-bit dividend is zero. Such restrictions make high-precision calculations more difficult.

ShreevatsaR
  • 38,402
  • 17
  • 102
  • 126