Re: Constant divisions, remainders

henry@zoo.toronto.edu (Henry Spencer):
> Actually, I seem to recall that it is specifically a relic of FORTRAN,
> which made a fairly arbitrary decision for the sake of well-defined
> behavior, and has been too influential for machine designers to ignore
> ever since.


Indeed, there are two "intuitive" ways to solve the problem of negative
operands in the system:


      Q = A div B
      R = A mod B


While adhering to the rule that


1) A = QB + R


One solution preserves the equation:


2) (-A)/B = -(A/B)


The desirability of this equation is obvious!


While the other preserves the rule that


3) sign(R) = sign(B)


The desirability of this equation is also obvious -- it makes
modular arithmetic work, specifically, either


0 <= A mod B < B -- for positive B


or


0 >= A mod B > B -- for negative B


Rules 1, 2 and 3 are all desirable, but they cannot all be satisfied! The
designers of FORTRAN, being numerically inclined, chose to keep rule 2,
and they didn't really think about 1. Wirth, in Pascal, chose to keep 2
because of precidents, and also added rule 1 to define the mod operator.
Ada provided a mod operator that satisfied rule 3, but also a rem operator
so that they could define div and rem in terms of 1 and 2. The average
Ada programmer probably flips a coin to select between the mod and rem
operators.


Speaking as someone who worries primarily about coding and other integer
stuff, I'd prefer division to obey rules 1 and 3, because then I can use
div and mod to pack and unpack things to an arbitrary radix.


If hardware designers need a hard and flat statement to guide their work,
it should be that both definitions of div and mod should be supported by
the hardware! (or in a RISC, if neither is supported, I should be able to
get either).


In my PhD thesis, long ago, I suggested that the div instruction (that
produces both quotient and remainder) should provide one interpretation,
but that there should be a single instruction that can be used to flip
between rule 2 and 3 -- I called this the divide correct instruction.
checks the condition codes (or whatever) and if needed adjusts the
quotient up or down by one and adjusts the remainder by adding or
subtracting the divisor.
Doug Jones
jones@cs.uiowa.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.