Integer Modulus vs. RemainderDate: 03/14/2002 at 10:44:22 From: Roger Subject: INTEGER MODULUS vs. REMAINDER I've read this discussion: Mod Function and Negative Numbers http://mathforum.org/dr.math/problems/anne.4.28.99.html What is the correct value for the function MOD(-340,60)? Microsoft Excel returns the value 20, while Lotus 1-2-3 returns the value -40. Can you explain the difference? The difference between REMAINDER and MODULUS, for us computer types, is a difficult one, because we were all taught by our professors that the MODULUS is the REMAINDER of an INTEGER division. But your discussion leads me to believe this is not quite true. The computerized MOD() or "%" in C, the REMAINDER, is simply this: REM(N, D) { return N - D * (N / D) ; } Can we therefore say the MODULUS is: MOD(N, D) { return REM( D + REM( N, D ), D ) ; } This would be for ALL values, in the "N" and all NON-ZERO values in the "D". I've implemented it this way, specifically, to avoid any non-algebraic expressions. And sticking with that restriction, these are the only ways (that I know of) to implement the two functions, using PURE ALGEBRAIC NOTATION (no "if/else/</>/etc) involved). Am I correct in my interpretations? Are there better, more efficient, ways to implement these functions in ALGEBRA? Thank you very much in advance, Roger Date: 03/14/2002 at 12:41:23 From: Doctor Peterson Subject: Re: INTEGER MODULUS vs. REMAINDER Hi, Roger. If I assume that you are writing in C, and that your compiler, like most if not all today, truncates integer division toward zero, then your function REM(N, D) { return N - D * (N / D) ; } should give exactly what N % D gives, and is indeed the remainder as I defined it. But as I said just below the table, since the direction of truncation, and therefore the meaning of "%", is not officially defined in C, it is not technically proper to define REM this way if you want to cover negative numbers. Now let's look at your MOD(N, D) { return REM( D + REM( N, D ), D ) ; } which in a well-behaved C is the same as MOD(N, D) { return ( D + N % D ) % D ; } This looks good for positive D; by adding D to N % D, you force the remainder from the interval (-D, D) to the interval (0, 2D), and then the second "% D" drops the range [D, 2D) back down to [0, D), restoring the original remainder for positive N. For negative D, we are adding a negative number, dropping the range down from (D, -D) to (-2D, 0), and then taking the remainder of this negative number with the negative divisor to shift the range (2D, D] up to (D, 0] and restoring the correct remainder for negative N. It looks right; I presume you tested it. It may be of interest to include the graphs of the remainder and modulus functions (as defined in Ada), which I looked at while I did the above analysis: Rem(x, 5): 5+ o o | / / | / / | / / | / / *---------*---------*---------*---------* -10 / -5 / 0 5 10 / / | / / | / / | o o -5+ Mod(x, 5): o 5o o o / / | / / / / | / / / / | / / / / | / / *---------*---------*---------*---------* -10 -5 0 5 10 Rem(x, -5): 5+ o o | / / | / / | / / | / / *---------*---------*---------*---------* -10 / -5 / 0 5 10 / / | / / | / / | o o -5+ Mod(x, -5): *---------*---------*---------*---------* -10 / -5 / 0 / 5 /10 / / | / / / / | / / / / | / / o o -5o o Note that these graphs represent the continuous analog of the mod and rem functions, so that they show line segments rather than just discrete points. The "*" represents a solid dot, meaning that that point IS in the graph, and the "o" represents an open dot, meaning that that point is NOT in the graph. Seeing the graphs this way gives a better sense of the "big picture" of the graph, though the actual graph would consist only of integer points (where the "*" and "/" are). And some languages do support this continuous form of either function. The fact that you are doing two remainders in order to get one mod does seem inefficient, and you could probably gain efficiency by using, say, a "?:" construct in C, but without that you probably can't do better. I like its simplicity. Thanks! - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/