Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: ANS TC Magnet for Division
Message-ID: <678.UUL1.3#5129@willett.UUCP>
Date: 19 Mar 90 02:52:37 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 85

Category 10,  Topic 17
Message 59        Sat Mar 17, 1990
R.BERKEY [Robert]            at 19:32 PST
 
 
  Re: Definition of mod as a binary operation.


The text below is from _Concrete Mathematics_, Graham, Knuth, Patashnik,
Addison-Wesley: 1989, pp. 81-82.

The notation for the floor (greatest integer) function used in the text isn't
in ASCII, the notation in the text uses left- and right-facing 'L's.  So, it's
transliterated as follows, and defined as per p. 67:

   floor(x) = the greatest integer less than or equal to x.


   ---------------------------------------------------------------

   3.4 'MOD': THE BINARY OPERATION

      The quotient of n divided by m is floor(n/m), when m and n
      are positive integers.  It's handy to have a simple notation
      also for the remainder of this division, and we call it
      'n mod m'.  The basic formula

        n  =  m * floor(n/m)  +  n mod m

      tells us that we can express  n mod m  as n - m * floor(n/m).
      We can generalize this to negative integers, and in fact to
      arbitrary real numbers:

      x mod y  =  x - y * floor(x/y),  for y <> 0           (3.21)

      This defines 'mod' as a binary operation, just as addition
      and subtraction are binary operations.  Mathematicians have
      used mod this way informally for a long time, taking various
      quantities mod 10, mod 2pi, and so on, but only in the last
      twenty years has it caught on formally.  Old notion, new
      notation.

         We can easily grasp the intuitive meaning of x mod y,
      when x and y are positive real numbers, if we imagine a
      circle of circumference y whose points have been assigned
      real numbers in the interval [0..y].  If we travel a distance
      x around the circle, starting at 0, we end up at x mod y.
      (And the number of times we encounter 0 as we go is
      floor(x/y).)

         When x or y is negative, we need to look at the definition
      carefully in order to see exactly what it means.  Here are
      some integer-valued examples:

         5 mod 3  =  5 - 3 * floor(5/3)         = 2;
        5 mod -3  =  5 - (-3) * floor(5/(-3))   = -1;
        -5 mod 3  =  -5 - 3 * floor(-5/3)       = 1;
       -5 mod -3  =  -5 - (-3) * floor(-5/(-3)) = -2.

      The number after 'mod' is called the _modulus_; nobody has
      yet decided what to call the number before 'mod'.  In
      applications, the modulus is usually positive, but the
      definition makes perfect sense when the modulus is negative.
      In both cases the value of x mod y is between 0 and the
      modulus:

         0  <=  x mod y  <  y,   for y > 0;
         0  >=  x mod y  >  y,   for y < 0.

      What about y = 0?  Definition (3.21) leaves this case
      undefined, in order to avoid division by zero, but to be
      complete we can define

         x mod 0  =  x                                   (3.22)

      This convention preserves the property that x mod y always
      differs from x by a multiple of y. ...

      ------------------------------------------------------------

and so on--this section continues for three more pages.

-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: 'uunet!willett!dwp' or 'willett!dwp@gateway.sei.cmu.edu'