Integer division

[Matthew P. Wiener]

In article <561 at jplgodo.UUCP> steve at jplgodo.UUCP (Steve Schlaifer x3171 156/224) writes:
>If you think of % as returning the *mathematical* remainder of a/b then
>it should return a value >=0.  On the other hand, to be consistent with this
>view, the quotient operator (/) will also have to be modified to preserve
>the formulae
>
>	b=qa+r (0<=r<a)
>	q=b/a
>
>i.e. (-3)/2 must be -2 if (-3)%2 is 1. But this then means that (|a|)/b is not
>the same as |a/b| for a<0.  Maybe *An Angry Number Theorist* wants this, but it
>seems to me to be a trap just waiting for the unwary to fall into.

[sic:  you go back and forth between a/b and b/a above  :-(]

But that's what we have been saying all along!  Someone doing integer division,
is not doing floating point division, and if he doesn't know that the rules are
different, then yes, he will fall into trouble.  There are several identities
running around that are incompatible.

 (1)	      a == (a/b) * b + a%b
 (2)	 (-a)/b == -(a/b)
 (3)	(a+b)/b == a/b + 1
 (4)	(a+b)%b == a%b

Notice that (3) and (4) are compatible with what the number theorists want,
but (2) isn't.  Sure the naive user is fooled by (2) under the version we
want, but then he's fooled by (3) and (4) in the usual version.  (1) holds
when the / and % are both what the number theorist wants or when neither are
what the number theorist wants.

>As for why the restriction of 0<=r<a was decided on, my only guess is that
>it then always produces a unique (q,r) for any given (a,b); this is a useful
>property when you are proving theorems or doing theoretical investigations.

That is correct.  It is also useful for programming a circular list.
------------------------------------------------------------------------------
Related question: what about floating to integer conversions?  That is always
done by truncating after the decimal point.  That always seemed wrong to me,
but it doesn't seem to bother me as much, and I can't remember a time when it
got in my way.  (unlike %)

ucbvax!brahms!weemba	Matthew P Wiener/UCB Math Dept/Berkeley CA 94720