Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!spool.mu.edu!agate!lima.berkeley.edu!bks From: bks@lima.berkeley.edu (Bradley K. Sherman) Newsgroups: comp.misc Subject: Re: Signed integer division - implementation questions Message-ID: <1991Jul1.032730.5608@agate.berkeley.edu> Date: 1 Jul 91 03:27:30 GMT References: <1991Jun29.172953.20536@ux1.cso.uiuc.edu> <1991Jun30.123047.3944@druid.uucp> Sender: usenet@agate.berkeley.edu (USENET Administrator) Organization: University of California at Berkeley Lines: 49 Someone says: ||I would prefer it if everyone would use the second system (remainder ||always non-negative), since it conforms most closely to the usual way ||mathematicians use modular arithmetic. I don't know if Donald Knuth counts as a mathematician, but in a book called _Concrete Mathematics_ he and two other authors say approximately: m mod n is well-defined for any integer values, positive and negative. (m mod 0 is often defined to be m.) Start with the relation: m mod n = m - n * floor(m/n) This insight yields this table [f(m/n) is floor(m/n)]: m n f(m/n) n*f(m/n) m mod n 13 5 2 10 3 -13 5 -3 -15 2 13 -5 -3 15 -2 -13 -5 2 -10 -3 Note that the sign of the result of m mod n matches the sign of the modulus. And someone else states (quoting K&R): | "Otherwise, [second operand not 0] it is always true that | (a/b)*b + a%b is equal to a." So combining the wisdom of Knuth, Kernighan and Richie we complete the table (here defining % to be the modulus operator as defined above): m n f(m/n) n*f(m/n) m%n m/n (m/n)*n + m%n 13 5 2 10 3 2 13 -13 5 -3 -15 2 -3 -13 13 -5 -3 15 -2 -3 13 -13 -5 2 -10 -3 2 -13 And everything hangs together. Note that % is _not_ defined as above in either K&R C or the ANSI standard. Both the remainder and division operations are machine dependent for negative operands and undefined if n is 0. % is referred to as the "remainder operator" in the standard. --------------------------------- Hope this helps, Brad Sherman (bks@alfa.berkeley.edu)