🚀 go-pugleaf

I apologize for my previous answer--I misread something Mr. Baker had
written. He came to the same conclusion as I for positive divisors.

Never mind.

Harlan Messinger

hbaker@netcom.com (Henry Baker) wrote:

>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.                                                   **


The 1990s: the Duh Decade