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