Path: utzoo!attcan!uunet!ns-mx!iowasp!deimos!ux1.cso.uiuc.edu!uwm.edu!rpi!zaphod.mps.ohio-state.edu!usc!snorkelwacker!bloom-beacon!eru!luth!sunic!mcsun!ukc!inmos!mph
From: mph@lion.inmos.co.uk (Mike Harrison)
Newsgroups: comp.theory
Subject: Re: Modulus (Re: hashing function for strings)
Message-ID: <4158@ganymede.inmos.co.uk>
Date: 22 Feb 90 11:24:05 GMT
References: <1990Feb15.211210.22950@max.sunysb.edu> <0ZqzBRm00WA1M0d5JZ@andrew.cmu.edu> <7416@ogicse.ogc.edu> <10940@saturn.ADS.COM>
Sender: news@inmos.co.uk
Reply-To: mph@inmos.co.uk (Mike Harrison)
Organization: INMOS Limited, Bristol, UK.
Lines: 48

In article <10940@saturn.ADS.COM> xanthian@saturn.ADS.COM (Metafont Consultant Account) writes:
>Yep.  It is utterly amazing how many modulus inplementations exist
>where (-1) mod m isn't m-1. 

In "Ada Language and Methodology", by David Watt, Brian Wichmann and William
Findlay, (pub. Prentice-Hall International).
[quoted without permission - sorry Brian!]

The following definitions are given for integer divide, rem and mod 
operations:

"The 'division operators' /, rem and mod are fairly straightforward when no
negative operands are involved.
...
The operator / always yields a result truncated, if necessary, towards zero.
In general:

        (-I)/J = -(I/J) = I/(-J)

The operators rem and mod always yield results smaller in magnitude than their
right operands. They are interchangeable unless their operands have opposite
signs. The difference is that rem always takes the sign from its left operand,
whereas mod always takes its sign from its right operand. They are defined by:

        I rem J = I - (I/J) * J

        I mod J = I - J * n     for some integer n such that 
                                    abs(I mod J) < abs J
                                and such that I mod J has the same sign as J
..."

Applying this to your example: (-1) mod m, and letting m = (say) 3, gives:

        (-1) mod 4 = (-1) - 4 * n, which for n = -1 yields

                   = (-1) - 4 * (-1)
                   = (-1) - (-4)
                   = (-1 + 4)  = 3
                   = m - 1

which appears to meet your case.

Mike,

Michael P. Harrison - Software Group - Inmos Ltd. UK.
-----------------------------------------------------------
UK : mph@inmos.co.uk             with STANDARD_DISCLAIMERS;
US : mph@inmos.com               use  STANDARD_DISCLAIMERS;