Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!talcott!harvard!seismo!brl-tgr!tgr!woody%Romeo@cit-hamlet.arpa
From: woody%Romeo@cit-hamlet.arpa
Newsgroups: net.lang.c
Subject: Mods and integer division
Message-ID: <2118@brl-tgr.ARPA>
Date: Fri, 31-Jan-86 17:34:58 EST
Article-I.D.: brl-tgr.2118
Posted: Fri Jan 31 17:34:58 1986
Date-Received: Mon, 3-Feb-86 04:55:48 EST
Sender: news@brl-tgr.ARPA
Lines: 35

>[On if (-a)%b == -(a%b) or (-a)%b >= 0 always?]
>Are there any good mathematical grounds for choosing one alternative over
>the other here? ... I want to know mathematically if one is better than the
>other.

  Being a Math/CS undergraduate here at Caltech, I sometimes get bitten
very hard by system designers who arbitrarly come up with a way of doing
math which is just wrong.  In an abstract algaebra class when we were talking
about group theory, we used the following definition for integer division:

   A / B = C  if and only if there exists R (R == A % B) such that
     (1)    (0 <= R) && (R < B)
     (2)    R + C * B == A

  When you use this definition, all sorts of nifty properties pop out of
group theory which apply to the study of numbers, such as algorithms for
determining if a large number is prime, or algorithms useful for encryption
codes.
  What bit me was this:  I spent four or five hours a couple of days ago
trying to figure out why my decryption routine was churning out garbage
delivered by my encryption routine.  Only after talking to my roommate
(a CS/EE type) did I find out I had to write:

        i = m % n;
        if (i < 0) i += n;       /* Turn 'i' into a true modulus result */

  Sure, it looks simple, but late in the evening, it can make us Math types
hate CS types enough to kill.  [And me a cross between both: I could have
killed myself for not seeing the obvious...]


         - William Woody
      NET  WOODY%ROMEO@HAMLET.CALTECH.EDU
   USMAIL  1-54 Lloyd; Caltech
           Pasadena, CA 91126