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

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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search