Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Integer Modulus vs. Remainder


Date: 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/   
    
Associated Topics:
High School Calculators, Computers

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/