Xref: utzoo sci.math:2801 comp.lang.modula2:626
Path: utzoo!utgpu!water!watmath!clyde!rutgers!mcnc!xanth!kent
From: kent@xanth.cs.odu.edu (Kent Paul Dolan)
Newsgroups: sci.math,comp.lang.modula2
Subject: MOD in Modula-2 flawed (was Re: perpetual calendar (also day of week))
Summary: Wirth's definition allows negative results
Keywords: munged
Message-ID: <4057@xanth.cs.odu.edu>
Date: 13 Feb 88 08:16:36 GMT
References: <8802101656.AA08424@decwrl.dec.com> <6413@j.cc.purdue.edu>
Reply-To: kent@xanth.UUCP (Kent Paul Dolan)
Organization: Old Dominion University, Norfolk Va.
Lines: 50

In article <6413@j.cc.purdue.edu> ags@j.cc.purdue.edu.UUCP (Dave
Seaman) writes: 
>In article <8802101656.AA08424@decwrl.dec.com> fulton@navion.dec.com
(10-Feb-1988 0957) writes: 
[lots omitted]

>>        Then you have -1 MOD 7  =>  -1,  which does not equate to any of
>>        the numbers assigned to Sunday thru Saturday, namely 0 thru 6. 

>I don't have my copy of the Modula-2 standard available at the moment, but
>I believe that the definition of the MOD operator is similar to Pascal,
>where the standard says:
>
>	A term of the form i mod j shall be an error if j is zero or
>	negative, otherwise the value of i mod j shall be that value of
>	(i-(k*j)) for integral k such that 0 <= i mod j < j.
>
>Therefore the correct value of (-1 MOD 7) is 6, not -1.  In fact, I believe
>that in Modula-2 the result of the MOD operator is type CARDINAL and
>therefore cannot be negative.  It sounds as if you may be stuck with a
>flawed implementation of Modula-2.

Sadly, the flaw is in Wirth's design, not Logitech's implementation.
I don't have his 3rd Edition Modula-2 reference manual handy (it's out
on loan), but I read it through in January, and was incredulous that
he would chose an implementation of MOD that is negative or zero to
the left of the origin (in y = x MOD modulus coordinates) and positive
or zero to the right of the origin, but there it was in print.  I
quickly took out my copy of the BENCHMARK Modula-2 compiler for the
Amiga, and wrote my first program to test this design flaw.  The
program worked as the book explained.  Aaaaargh.

I have run into the same problem in other languages (FORTRAN IV for
the HP 1000 many years ago comes to mind), and the work-around is
always the same: y = ((x MOD modulus) + modulus) MOD modulus.  Gag!

It appears Wirth was too seduced by the beauty of the "identity" x =
modulus * ( x DIV modulus ) + ( x MOD modulus ) [which is how he
defines MOD] to notice that the resulting modulus function is flawed
for any normal use (Life games on a 0..n-1 by 0..n-1 toroid, where the
value of cell (0,0) depends on the value of "cell" (-1 MOD n,-1 MOD n)
= (n-1,n-1), for example, or array-implemented ring queues, where one
wants to be able to index backward past the queue's origin and still
stay within the queue).  Even the giants have feet of clay, I guess.

I have been unable to communicate this problem to Dr. Wirth, so if one
of the European readers knows a forwarding address, by all means send
this note along to him.

Kent, the man from xanth.