division

[Henry Spencer]

> > >Almost but not quite true. A compiler CANNOT normally replace a divide
> > >by a right-shift if it is an integer divide. This is because a right
> > >shift of a negative integer is not the same as a divide.
> > 
> > However most useable processors provide arithmetic shifts which will give
> > the right result even if it is a signed divide.
> 
> The first is correct, the second is WRONG.  -1/2 is 0 not -1.

Ah, but is it?  It depends on whose definition of integer division you use.
The problem is that arithmetic shifts and conventional divide instructions
disagree.  Neither is inarguably "wrong".  Consider: what we want is a mapping
<a,b> -> <q,r>, where q*b+r = a and |r|<|b|.  When r != 0, there is more than
one such mapping.  For positive numbers there is general consensus on which
is wanted:  keep everything positive.  When negative numbers enter the scene
explicitly, it's not so clear.  Even with a constraint of being consistent
with the positive-numbers rule, there is an ambiguity:  do you truncate
the quotient toward zero, or toward negative infinity?  For negative numbers,
these give different answers.  Truncation toward negative infinity is more
highly regarded by mathematicians (ask a mathematician what the value of
"-1 mod 2" is, and then figure out which kind of division that is consistent
with), and is what two's-complement arithmetic shifts do.  Truncation toward
zero is what most languages and machines do, following the lead of Fortran
and the 709.  Hence the mess.

There are exceptions.  CLU defined integer division as negative-infinity
style, and the manual noted (as a bug!) that some implementations did it
the other way.  The 32032 gives you your choice.

The value of -1/2 depends on whether you mean -(1/2) [definitely 0] or
(-1)/2 [it depends].
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry