Xref: utzoo comp.theory:349 comp.misc:8222 comp.lang.misc:4129
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucsd!ames!saturn!xanthian
From: xanthian@saturn.ADS.COM (Metafont Consultant Account)
Newsgroups: comp.theory,comp.misc,comp.lang.misc
Subject: Re: Modulus (Re: hashing function for strings)
Message-ID: <10946@saturn.ADS.COM>
Date: 19 Feb 90 11:59:58 GMT
References: <1990Feb15.211210.22950@max.sunysb.edu> <0ZqzBRm00WA1M0d5JZ@andrew.cmu.edu> <7416@ogicse.ogc.edu> <10940@saturn.ADS.COM>
Organization: Advanced Decision Systems, Mt. View, CA (415) 960-7300
Lines: 39
In article flee@shire.cs.psu.edu (Felix Lee) writes:
>Kent Paul Dolan wrote:
>>Yep. It is utterly amazing how many modulus inplementations exist
>>where (-1) mod m isn't m-1.
>
>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
>
>Unfortunately, they're mutually contradictory. You must choose one of
>them to violate. Someone will be unhappy with your decision.
Absolutely! One may either choose to truncate integer divisions'
quotients towards minus infinity, a very unnatural feeling operation,
to dissociate the modulus function from the remainder of integer
division, or to violate the grade school concept of reconstructing the
dividend simply from the divisor, the quotient, and the remainder.
I see the idea of a modulus function that doesn't change if the axis
is shifted left or right by the mod base, rather than one that suffers
an ugly reflection at the origin, as inherently beautiful, in the math
sense. It is also inherently more useful, in the graphics programming
sense.
Among your three items, the one that does not arouse any particular
religious fervor at thoughts of its loss is the second; I see no
particular reason to identify the mod function with the remainder of
integer division; they are very comfortable as independent concepts,
and, I think, were identified with one another on computers by the
historical accident that the remainder fell out simply from the most
common implementation of shift and subtract logic for division, which
leaves the remainder in one half of the dividend double register while
the quotient is built in the other half, and the by arithmetical
coincidence that they are identical when all the operands are
positive.
--
xanthian@ads.com xanthian@well.sf.ca.us (Kent Paul Dolan)
Again, my opinions, not the account furnishers'.