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
_____________________________________________

Mod Function and Negative Numbers


Date: 04/28/2000 at 11:17:09
From: Anne
Subject: Using the mod() function with negative numbers

I work in IT - Technical Support. I am trying to sort out a problem 
for a user who is using the MOD() function in Excel 97 as follows:

     =MOD(-340,60)

He thinks it should return a value of 40, but it returns a value of 
20.

It returns a value of 40 if we do the following:

     =MOD(340,60)

Now I am wondering why the negative sign makes a difference. You can 
see from my age that it was years ago that I had math, and I was very 
good at it. But I cannot remember how negative numbers work in 
division.

Can you help me?

Anne


Date: 04/28/2000 at 12:57:10
From: Doctor Peterson
Subject: Re: Using the mod() function with negative numbers

Hi, Anne.

There are different ways of thinking about remainders when you deal 
with negative numbers, and he is probably confusing two of them. The 
mod function is defined as the amount by which a number exceeds the 
largest integer multiple of the divisor that is not greater than that 
number. In this case, -340 lies between -360 and -300, so -360 is the 
greatest multiple LESS than -340; we subtract 60 * -6 = -360 from -340 
and get 20:

-420 -360 -300 -240 -180 -120  -60   0   60   120  180  240  300  360
--+----+----+----+----+----+----+----+----+----+----+----+----+----+--
       | |                                                    |  |
   -360| |-340                                             300|  |340
       |=|                                                    |==|
        20                                                     40

Working with a positive number like 340, the multiple we subtract is 
smaller in absolute value, giving us 40; but with negative numbers, we 
subtract a number with a LARGER absolute value, so that the mod 
function returns a positive value. This is not always what people 
expect, but it is consistent.

If you want the remainder, ignoring the sign, you have to take the 
absolute value before using the mod function.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   


Date: 05/02/2000 at 04:58:50
From: Norwich C.C. Network Services
Subject: Re: Using the mod() function with negative numbers

Thanks very much for sorting this out. I had worked out how it was 
arriving at the result, but did not know whether it was correct. We 
had also tried it in Lotus 1-2-3 and the result given was -40, which 
was what the user expected. Nice to have built some user confidence in 
Excel.

Thanks again for your help.

Anne


Date: 05/02/2000 at 17:16:19
From: Doctor Peterson
Subject: Re: Using the mod() function with negative numbers

Hi, Anne.

It occurs to me that I don't quite want to leave you trusting Excel 
too much. A comment I had considered making before was that a program 
may often use its own definitions for functions like this, and 
apparently Lotus proves my point that "mod" can be taken in different 
ways. You should always go by the manual, not by what a mathematician 
says.

Excel has its own share of mathematical foibles; here's a copy of an 
answer I gave to someone who asked about its handling of -a^b:

     ===========================================================

The proper rule is that negation has the same precedence as 
multiplication and division. After all, negation means multiplication 
by -1. So -a^b should be taken as -(a^b). You can read more how Excel
handles that calculation in this note from our archives:

  Order of Operations and Negation in Excel
  http://mathforum.org/library/drmath/view/69058.html

Some time ago when I was researching order of operations for another 
inquiry, I ran across this page from Microsoft explaining this quirk:

    XL: Order of Precedence Causes Unexpected Positive Value

   http://support.microsoft.com/support/kb/articles/Q132/6/86.asp   

It doesn't claim that their rule agrees with the mathematical world, 
only that they make their own standards, and don't have to agree with 
anyone:

  This behavior is by design of Microsoft Excel. Microsoft Excel uses
  an order of calculation to evaluate operators in formulas. The order
  of evaluation of operators dictates that a minus sign (-) used as a
  negation operator (such as -1) is evaluated before all other
  operators. Because of this order, the formula =-1^2 represents the
  value -1 squared, and returns the value 1, a positive value.
   ...
  Note that this has been the standard method for evaluating formulas
  since the first version of Microsoft Excel.

  NOTE: This order of operation is different from the order of
  operation in Lotus 1-2-3.

What I suspect is that the programmers were accustomed to the C 
language, in which unary operators such as negation have higher 
precedence than any binary operator; there is no exponent operator in 
C. When they added the exponent operator, they may simply have 
forgotten that it should have higher precedence, or they may have 
found it was easier to program this way. Once the rule became 
established, they couldn't change it and make customer's programs 
fail.

There are many other instances where calculators or software make 
their own rules; sometimes this is because of limitations of their 
interface, sometimes because of a misguided desire to "improve" the 
rules. In any case, we can't use any piece of software as our guide to 
mathematical practice, and students should be taught not to confuse 
the rules of a particular program with those of math. We wouldn't want 
Microsoft to be making these decisions for us anyway, would we?

===========================================================

So the score is Microsoft 1, Lotus 1!

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   


Date: 05/03/2000 at 08:53:33
From: Norwich C.C. Network Services
Subject: Re: using the mod() function with negative numbers

Thanks for that!

I will remember not to trust Excel too much.

Anne


Date: 07/05/2001 at 13:58:23
From: A. H. Banen
Subject: Mod Function and Negative Numbers

Dear Dr. Peterson,

Concerning the topic "Mod Function and Negative Numbers," I found it 
strange you did not refer to the simple rule concerning integer 
division and modulo calculation: Given the integer numbers A and B
(where B cannot be equal to zero), the following holds:

A = ( A DIV B ) * B  +  A MOD B

e.g. for A = 340 and B = 60
A = ( 340 DIV 60 ) * 60  +  ( 340 MOD 60 )  =>
A = (      5     ) * 60  +        40        =>
A = 340

Also, when A = -340 and B = 60
A = ( -340 DIV 60 ) * 60 + ( -340 MOD 60 )
A = (      -5     ) * 60 + (      -40    ) =>
A = -340

From this can be derived that MOD(-340, 60) should have been -40

Sincerely,
Andre Banen


Date: 07/05/2001 at 16:17:04
From: Doctor Peterson
Subject: Re: Mod Function and Negative Numbers

Hi, Andre.

You're right that this relation is relevant to the question; below
I'm going to include a more detailed answer.

But it only proves what MOD should do _if_ we know how DIV is defined;
that is, it is a statement of consistency between the mod function and
the direction of integer truncation. You're _assuming_ truncation
toward zero, so that -340/60 gives -5. But in Excel, we see that the
relation looks like this:

     A = ( -340 DIV 60 ) * 60 + ( -340 MOD 60 )
  -340 =       -6        * 60 +        20

This is perfectly consistent if their integer division truncates
toward -infinity rather than toward zero, so that -340/60 is taken to
be -6. And that's just what I said, using words rather than the
formula:

    The mod function is defined as the amount by which a number
    exceeds the largest integer multiple of the divisor that is
    not greater than that number. In this case, -340 lies between
    -360 and -300, so -360 is the greatest multiple LESS than -340;
    we subtract 60 * -6 = -360 from -340 and get 20.

So in fact I did refer to your rule.

Here's a more complete answer:

Computer languages and libraries are notoriously inconsistent, or at
least unmathematical, in their implementation of "mod" for negative
numbers. There are several ways it can be interpreted in such cases,
and the choice generally made is not what a mathematician would
probably have made. The issue is what range of values the function
should return. Mathematically, we define "modulo" not as a function,
but as a relation: any two numbers a and b are congruent modulo m if
(a - b) is a multiple of m. If we want to make a function of this, we
have to choose which number b, of all those that are congruent to a,
should be returned.

Properly, the modulus operator a mod b should be mathematically
defined as the number in the range [0,b) that is congruent to a, as
stated here:

    http://mathworld.wolfram.com/ModulusCongruence.html   

    In many computer languages (such as FORTRAN or Mathematica), the 
    common residue of b (mod m) is written mod(b,m) (FORTRAN) or 
    Mod[b,m] (Mathematica).

    http://mathworld.wolfram.com/CommonResidue.html   

    The value of b, where a=b (mod m), taken to be nonnegative and 
    smaller than m.

Unfortunately, this statement about FORTRAN, and implicitly about the
many languages that have inherited their mathematical libraries from
FORTRAN, including C++, is not quite true where negative numbers are
concerned.

The problem is that people tend to think of modulus as the same as 
remainder, and they expect the remainder of, say, -5 divided by 3 to
be the same as the remainder of 5 divided by 3, namely 2, but negated,
giving -2. We naturally tend to remove the sign, do the work, and put
the sign back on, because that's how we divide. In other words, we
expect to truncate toward zero for both positive and negative numbers,
and have the remainder be what's left "on the outside," away from
zero. More particularly, computers at least since the origin of
FORTRAN have done integer division by "truncating toward zero," so
that 5/2 = 2 and -5/2 = -2, and they keep their definition of "mod" or
"%" consistent with this by requiring that

    (a/b)*b + a%b = a

so that "%" is really defined as the remainder of integer division as 
defined in the language.

Because FORTRAN defined division and MOD this way, computers have
tended to follow this rule internally (in order to implement FORTRAN
efficiently), and so other languages have perpetuated it as well. Some
languages have been modified more recently to include the more
mathematical model as an alternative; in fact, FORTRAN 90 added a new
MODULO function that is defined so that the sign of MODULO(a,b) is
that of b, whereas the sign of MOD(a,b) is that of a. This makes it
match the mathematical usage, at least when b is positive.

Similarly, in Ada there are two different operators, "mod" (modulus) 
and "rem" (remainder). Here's an explanation with plenty of detail:

    Ada '83 Language Reference Manual - U.S. Government
    http://archive.adaic.com/standards/83lrm/html/lrm-04-05.html   

    Integer division and remainder are defined by the relation 

        A = (A/B)*B + (A rem B) 

    where (A rem B) has the sign of A and an absolute value less than 
    the absolute value of B. Integer division satisfies the identity 

        (-A)/B = -(A/B) = A/(-B) 

    The result of the modulus operation is such that (A mod B) has the 
    sign of B and an absolute value less than the absolute value of B; 
    in addition, for some integer value N, this result must satisfy 
    the relation 

        A = B*N + (A mod B) 

    ...
    For positive A and B, A/B is the quotient and A rem B is the 
    remainder when A is divided by B. The following relations are 
    satisfied by the rem operator: 

        A    rem (-B) =   A rem B
        (-A) rem   B  = -(A rem B) 

    For any integer K, the following identity holds: 

        A  mod   B  =  (A + K*B) mod B 

    The relations between integer division, remainder, and modulus are
    illustrated by the following table: 

 A   B   A/B   A rem B  A mod B     A     B    A/B   A rem B   A mod B

10   5    2       0        0      -10     5    -2       0         0
11   5    2       1        1      -11     5    -2      -1         4
12   5    2       2        2      -12     5    -2      -2         3
13   5    2       3        3      -13     5    -2      -3         2
14   5    2       4        4      -14     5    -2      -4         1

10  -5   -2       0        0      -10    -5     2       0         0
11  -5   -2       1       -4      -11    -5     2      -1        -1
12  -5   -2       2       -3      -12    -5     2      -2        -2
13  -5   -2       3       -2      -13    -5     2      -3        -3
14  -5   -2       4       -1      -14    -5     2      -4        -4

So what's the conclusion? There are basically two models, reasonably 
distinguished in Ada terms as Remainder and Mod; the C++ "%" operator
is really Remainder, not Mod, despite what it's often called.
Actually, its behavior for negative numbers is not even defined
officially; like many things in C, it's left to be processor-dependent
because C does not define how a processor should handle integer
division. Just by chance, all compilers I know truncate integers
toward zero, and therefore treat "%" as remainder, following the
precedent of FORTRAN. As _C: A Reference Manual_, by Harbison and
Steele, says, "For maximum portability, programs should therefore
avoid depending on the behavior of the remainder operator when 
applied to negative integral operands."

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   


Date: 07/06/2001 at 04:22:22
From: A. H. Banen
Subject: Re: Mod Function and Negative Numbers

Dear Dr. Peterson,

I must concur with almost of your reasoning with one exception: you state I
have a _presumption_ about truncation towards zero. But, toward the end of
the very complete answer you sent me, you quote from
references found in the Ada '83 Language Reference Manual that integer
division has to satisfy the identity (-A)/B = -(A/B) = A/(-B). When this
identity is observed there is only one correct outcome of the integer divison
-340/60 (i.e. -5).

I can only hope that the identities the above site states to be
satisfied by integer devision, remainder and modulo function, are not the
presumption used by the definition of Ada, but that these are fundamental
identities all calculus is based on. I really hope you can confirm the
latter, as the trouble I had finding valid definitions of integer division,
etc. on the Internet really bothers me.

Also, the links you quoted to MathWorld (mathworld.wolfram.com) are no
longer valid, which is very disappointing as Wolfram really has given
mathematics on the computer its rightful place.

And thank you for your answer.

Sincerely,
Andre Banen


Date: 07/06/2001 at 09:05:12
From: Doctor Peterson
Subject: Re: Mod Function and Negative Numbers

Hello again!

I am aware that MathWorld has been unavailable for some time; we have left
links to it in many places, hoping that it will come back. I was very glad
that I had quoted from it rather than just giving a link.

I called "truncation toward zero" a presumption with regard to how Excel or
any other program should work; the developers of any particular programming
language or program are free to define conversion from "real" to integer in
any way they choose, as long as they define it. There is certainly no
presumption that those developers always make the mathematically "proper"
choices, since they may have different goals. The fact is that both forms of
truncation make sense in different applications; both "remainder" and
"modulo" are useful. Therefore it would be wrong to claim that only one is
valid. As I said, "Mod" is more mathematical, and there are many 
formulas for which it is necessary (causing great difficulties for C 
programmers); but "Rem" is useful in other cases, particularly since it is
consistent with the most natural definition of integer division. You show a
preference for Rem, and I won't argue against you, as long as you recognize
that Mod has its place as well.

Note that the identity you refer to is used in Ada only to define integer
division, and that Rem is defined from that; Mod is defined separately, but
is consistent with the "greatest integer" formulation of integer division,
which does not satisfy that identity. There is no reason it should; it has
different purposes.

I think the provision of two formulations as in Ada is reasonable, and would
not try to prove that one is invalid. The fact is that there is no definition
of "integer division" in math; rather, we divide and apply the greatest
integer function or some variation of it to the resulting rational number,
depending on our needs. Integer division is a formulation of computer
languages, and they define it for their own use.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School About Math
High School Calculators, Computers
High School Negative Numbers
High School Number Theory
Middle School About Math
Middle School Negative Numbers

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/