Xref: utzoo comp.theory:359 comp.misc:8253 comp.lang.misc:4181
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!mucs!chl
From: chl@cs.man.ac.uk (Charles Lindsey)
Newsgroups: comp.theory,comp.misc,comp.lang.misc
Subject: Re: Modulus (Re: hashing function for strings)
Message-ID: <981@m1.cs.man.ac.uk>
Date: 20 Feb 90 11:38:05 GMT
References: <1990Feb15.211210.22950@max.sunysb.edu> <0ZqzBRm00WA1M0d5JZ@andrew.cmu.edu> <7416@ogicse.ogc.edu> <10940@saturn.ADS.COM> <E1wt*4@cs.psu.edu> <10946@saturn.ADS.COM>
Organization: Dept. Of Comp Sci, Univ. of Manchester, UK.
Lines: 71

xanthian@saturn.ADS.COM (Metafont Consultant Account) writes:

>In article <E1wt*4@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes:
>>There are three things that most people would like:
>>	quotient = -5 div 3 = -(5 div 3) = -1
>>	remainder = -5 mod 3 = (-5 + 6) mod 3 = 1
>>	3*quotient + remainder = -5

>Absolutely!  One may either choose to truncate integer divisions'
>quotients towards minus infinity, a very unnatural feeling operation,

On the contrary, one must start by realising that it is the usual definition
of integer division in programming languages that is WRONG, and is the real
root of the problem.

Also, aipdc@castle.ed.ac.uk (Paul D. Crowley) writes:

>I'd _hate_ a computer that obeyed the first of these. To me, -5 div 3 is
>-2. -5 div 3 = int(-5/3) = int(-1.666) = -2

So I am not alone in my view.

Here is a nice example taken from an article by Lambert Meertens in ALGOL
Bulletin #39. I have transcribed it into ADA,

TYPE intarray IS ARRAY(integer RANGE <>) OF integer;

PROCEDURE mid(a: intarray) RETURN integer IS
		-- the "middle" value of the array a
	BEGIN RETURN a( (a'first + a'last)/2 ) END;

PROCEDURE at(a: intarray, newbound: integer) RETURN intarray IS
		-- a copy of a, s.t. a'first = newbound
	DECLARE
		newa: ARRAY(newbound .. a'last-a'first+newbound) OF integer := a;
	BEGIN RETURN newa; END;

somearray: intarray(1..4) := (1,2,3,4);

	-- so mid(somearray) gives '2'

FOR i IN REVERSE -4..+4
LOOP	put(mid(at(somearray, i))); END LOOP;
	-- prints "2 2 2 2 2 2 3 3 3"


How did we get into this mess? Once upon a time (c. 1950) some machines
(mostly in Europe) did integer division "right" and some (mostly in America)
did it "wrong". The difference was essentially between machines built by
mathematicians and machines built by engineers (note that, if you carefully
follow a textbook on Algebra, you will see how mathematicians treat it). Not
surprisingly, the "wrong" answer got built into FORTRAN. The last chance to
get it right was in ALGOL 60, when the Europeans were only interested in REAL
division. The Americans wanted a separate operator for INTEGER division, so
the Europeans asked the Americans to provide a definition for it.

I tried in 1968 to get it right in ALGOL 68, but all I achieved was to get the
MOD correct (and not the same as remainder).

I tried to persuade ADA to get it right, but all I achieved was to get a REM
operator in addition to MOD.

I tried to get the PASCAL standardizers to get it right, but although they
admitted the merit of my case, they got cold feet because, in the meantime,
all hardware was now being built the way languages were now defining it.


So here is my plea to our descendants who may someday colonize a planet in
Alpha Centauri. When you get there, and set up new standards to be applied in
that corner of the galaxy, please remember that the people on Terra got
integer division WRONG, and do not let the mistake propagate any further.