Beware: Hackers - (nf) - integer division

[Henry Spencer]

Rob Warnock observes:

  Not only will "negative_int >> n"  give you a terribly wrong answer
  (compared to "negative_int / (2**n)") if your machine uses logical shift,
  but it will give you an "off by one" answer if you use arithmetic shift
  (unless negative_int happens to be minus a power of 2 bigger than "n").

Actually, if the machine is using arithmetic shift the shift is arguably
right and the "true" division wrong.  The problem is that there is
no unique "right" definition of integer division for the case where the
remainder is nonzero. The basic problem is to define a function n div d
(where n and d are integers) that yields an ordered pair of integers <q, r>
such that q*d + r == n && |r| < |d|.  The problem is that there is more
than one such function.  The four most obvious possibilities can be summed
up in terms of their effects on a non-zero remainder:

	1. Remainder has same sign as dividend.
	2. Remainder has same sign as divisor.
	3. Remainder is always positive.
	4. Magnitude of remainder is minimized, with some decision rule
		for resolving ties (e.g. 5 div 2 == <2, 1> or <3, -1>).

3 is a bit odd.  4 is rounding, which is usual for floating-point
but odd for integers.  The major candidates are 1 and 2.  1 is the
Fortran approach, truncating the quotient towards 0.  Most languages
and most machines have followed Fortran's lead.  2 is "modulus division",
with the quotient truncated toward minus infinity.  This is the division
operation implemented by arithmetic shifts on a two's-complement machine.
Modulus division is possibly superior to Fortran division, in fact, and
some recent languages and one recent machine (the 16032) recognize this.
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry