Integer division

[Frank Adams]

We seem to agree that there are three at least somewhat important identities.

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

As a mathematician and as a computer scientist, I cannot accept definitions
of these functions for which (1) does not hold.  Given (1), the two forms
given for (2) and (3) are equivalent.

Now, in fact, (3) in the division form is important.  The area I know of
where it is important is in financial applications.  Suppose I own 200
shares of stock, which I purchased at a total cost of $2,098.75, including
commission.  I now sell 100 shares.  I have to compute the cost basis for
those 100 shares: $1,049.38.  Now, suppose I had a short position with the
same cost basis: -$2,098.75.  If I buy back half of these, the rounding
has to be done the same way: -$1,049.38.

Of course, this application is not rounding toward zero; it is rounding
to the *nearest* penny.  So what we want for this application is to round
to the nearest integer, with 1/2 rounded away from zero.  This choice is
very common in financial applications.  (By the way, financial applications
fairly often divide by negative numbers.)

There are also a lot of number theoretic algorithms which run faster if
the least absolute remainder is used; I once heard a professor of
mathematics (Hans Zassenhaus, if memory serves) state that the least
absolute remainder is what computer division *should* return.

I believe that computers (CISC) and programming languages should provide
at least three different division and remainder operations: round towards
0, round towards -infinity, and round to nearest (with 1/2 rounded away
from 0).  There is something to be said for round away from zero, and
round to +infinity, as well.

Frank Adams                           ihpn4!philabs!pwa-b!mmintl!franka
Multimate International    52 Oakland Ave North    E. Hartford, CT 06108