🚀 go-pugleaf

This problem has been discussed ad nauseum in every single comp.lang
newsgroup, and it seems to be that every language gets it wrong in the
first n iterations, so that the implementers of the new languages keep
copying the wrong code from their previous language.

The usual justification for getting it wrong is that 'that's what the
hardware does, and we want fast code'.  Of course, once the language gets
established and _portability_ to a wide variety of machines becomes important,
it becomes necessary to try to retrofit a fully specified function, thus
breaking many existing programs.

So far as I know, only APL and Common Lisp have attempted to get 'mod' right.

'Everybody' thinks they know how division works, because they all learned it
in graded school.

OK, so what did you learn?  Given a 'dividend' N and a 'divisor' D, we need
to compute a 'quotient' Q, and a 'remainder' R.  What properties do we want
from this quotient Q and this remainder R?

The first property is that N = Q*D + R.  Otherwise, the whole meaning of
'remainder' is lost -- i.e., that part that 'remains' after taking out Q
copies of D from N.

Fine, so we simply set Q=0, R=N.  'You can't do that," you say.  Why?  Because
then division didn't _do_ anything, it didn't make R 'small'.

Why do we need R 'small'?  Well, if we're converting binary to decimal, and
we divide our binary number by 10 and get as a remainder our original binary
number, we will need an awful lot of decimal 'digits' :-).  So, using base
conversion as a _criterion_, we add the additional constraint that

0 <= |R| < |D|.

In other words, we want the absolute value of the 'remainder' to be smaller
than the absolute value of the divisor.

However, this still doesn't pin down the answer.  For example, if we divide
27 by 10, we can get two different quotients and remainders:

(I)     27 = 2*10 + 7         i.e., Q=2, R=7

(II)    27 = 3*10 + (-3)      i.e., Q=3, R=-3

Going back to our decimal conversion problem again, we decide that the
most appropriate choice is the first, not the second, since we want base
conversion to 'work' correctly.

We therefore refine our constraints, but find that we still have two choices
when the divisor is _negative_.

(I)     0 <= R < |D|

(II)    0 <= R*D < D^2

For example, if we divide 27 by -10, we can still get two different quotients
and remainders:

(I)     27 = (-2)*(-10) + 7     i.e., Q=-2, R=7

(II)    27 = (-3)*(-10) + (-3)  i.e., Q=-3, R=-3

Once again, we appeal to the base conversion algorithm for our answer.  In
the case of a negative divisor, we _expect_ negative digits -- indeed, we
_demand_ them, so that the correct choice is (II), which can be expressed
by the rule "sign of remainder follows sign of the divisor" (NOT, sign of
the dividend, like lots of brain-damaged computer hardware).

The nice thing about the "sign of the divisor" choice is that the quotient
is easily expressed as the 'floor' function:  Q = floor[N/D].

----

There is another division function called 'round' which tries to find the
'closest' integer to the rational quotient.  As might be expected, the
remainders produced by 'round' are smaller than those produced by 'floor',
and are both positive and negative:

0 <= |R| <= |D|/2

This is well-defined if D is an odd integer, but is ambiguous if D is even.
There are several competing definitions for what to do if D is even: one of
them is 'if N/D falls half way between two integers, choose the even one
as the quotient'.  This rule is similar to one that is used by numerical
analysts as an 'unbiased' rounding rule, and is used by some IEEE float
implementations.

Base conversion sometimes uses remainders produced by 'round' instead of
'floor'.  For example, hardware multipliers often convert to a 'balanced'
notation.  If we were doing decimal, then we would use the 'digits'
-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, instead of 5, 6, 7, 8, 9, 0, 1, 2, 3, 4,
respectively, because it reduces the number of carries that have to propagate.

(Those who know about implementations of GCD, also know that 'round' produces
the GCD in the least number of iterations.)

-----

To summarize, the 'correct' mod is one that produces remainders that follow
the _divisor_, and therefore the 'correct' quotient is the _floor_ function.
If your language allows more than one, then the next one should be the
'round' function (& least absolute remainders).

Unless you plan for your language to run on only one machine, make the
quotient and mod functions _well-defined_, so that portability is ensured.

----

You might find additional insight in the paper

ftp://ftp.netcom.com/pub/hb/hbaker/Gaussian.html  (also .ps.Z)

-- 
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html

Copyright (c) 1996 by Henry G. Baker.  All rights reserved.
** Warning: Due to its censorship, CompuServe and its subscribers **
** are expressly prohibited from storing or copying this document **
** in any form.                                                   **