c++standardsmodulolanguage-design

Why does C++ output negative numbers when using modulo?


Math

If you have an equation like this:

     x mod 7 = 3

x could be ... -4, 3, 10, 17, ..., or more formally:

     x = 3 + k * 7

where k can be any integer. I don't know if a modulo operation is defined for math, but the factor ring certainly is.

Python

In Python, you will always get non-negative values when you use % with a positive m:

m = 7

for i in range(-8, 10 + 1):
    print(i % 7, end="   ")

results in:

6   0   1   2   3   4   5   6   0   1   2   3   4   5   6   0   1   2   3

C++

#include <iostream>

int main() 
{
    int m = 7;

    for (int i = -8; i <= 10; i++)
        std::cout << (i % m) << "   ";
}

will output:

-1   0   -6   -5   -4   -3   -2   -1   0   1   2   3   4   5   6   0   1   2   3

ISO/IEC 14882:2003(E) - 5.6 Multiplicative operators:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined 74).

and

  1. According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.

Source: ISO/IEC 14882:2003(E)

(I couldn't find a free version of ISO/IEC 1539:1991. Does anybody know where to get it from?)

The operation seems to be defined like this:

enter image description here

Question:

Does it make sense to define it like that?

What are arguments for this specification? Is there a place where the people who create such standards discuss about it? Where I can read something about the reasons why they decided to make it this way?

Most of the time when I use modulo, I want to access elements of a datastructure. In this case, I have to make sure that mod returns a non-negative value. So, for this case, it would be good of mod always returned a non-negative value. (Another usage is the Euclidean algorithm. As you could make both numbers positive before using this algorithm, the sign of modulo would matter.)

Additional material:

See Wikipedia for a long list of what modulo does in different languages.


Solution

  • On x86 (and other processor architectures), integer division and modulo are carried out by a single operation, idiv (div for unsigned values), which produces both quotient and remainder (for word-sized arguments, in AX and DX respectively). This is used in the C library function divmod, which can be optimised by the compiler to a single instruction!

    Integer division respects two rules:

    Accordingly, when dividing a negative number by a positive number, the quotient will be negative (or zero).

    So this behaviour can be seen as the result of a chain of local decisions: