Why is operator% referred to as the “modulus” oper

问题:

Today at work I had an interesting discussion with one of my coworkers. He was surprised when he had the following happen to him:

assert(-1 % 10 == -1)  //Expecting 9

So when he came to ask me about it, I told him "well, that makes sense. When you divide -1 by 10, you get 0 with -1 remaining. His argument however was that the modulus operator is supposed to hold true to the "always positive" model. I did a little research and found that the modulus he was referring to looks like this:

Let q be the integer quotient of a and n. Let r be the remainder. Then:

a = n * q + r

The definition I was using, however, appears to be the Knuth version of modulus, which is:

Let q be the floor of a divided by n. Let r be the remainder. Then:

r = a - n * q

So, my question is why it ended up in the FORTRAN standard (and subsequently the C-standard) to have the modulus operator truncate toward 0? It seems like a misnomer to me to call it "modulus" and not "remainder" (In math, the answer really should be 9). Is this related to how hardware is doing the division?

For reference:

• Wikipedia on Modulus
• MSDN entry on the "modulus" operator
  (Yes, i realize its for VS2003...I'm stuck with it currently. Sadface)
• Modulus operator changes
• Don't assume positive remainder...

TLDR; Is hardware the reason the modulus operator truncates toward 0?

回答1:

It seems like a misnomer to me to call it "modulus" and not "remainder" (In math, the answer really should be 9).

C calls it the % operator, and calls its result the remainder. C++ copies this from C. Neither language calls it the modulus operator. This also explains why the remainder is negative: because the / operator truncates towards 0, and (a / b) * b + (a % b) should equal a.

Edit: David Rodríguez rightly points out that C++ does define a template class std::modulus, which calls operator%. In my opinion, that class is poorly named. Digging a little bit, it is inherited from STL where it was already named as it is now. The download for STL says "The STL was developed on SGI MIPSproTM C++ 7.0, 7.1, 7.2, and 7.2.1.", and as far as I can tell without actually having the compiler and hardware, MIPSpro passes the division to the CPU and MIPS hardware truncates to 0, which would mean std::modulus has always been misnamed.

回答2:

% is the remainder operator in C and C++.

In the C++ Standard, it is called the %operator and it yields the the remainder from the division. In the C Standard it is called the % operator and since C99 it is actually a remainder operator. The modulo and remainder operators differ with respect to negative values.

The % operator is defined in C and C++ with a == (a / b * b) + a % b.

Truncation of the integer division towards 0 in C is done since C99. In C89 it was implementation defined (and % can be a modulo operator in C89). C++ also performs truncation towards zero for integer division.

When truncation is done towards zero, % is a remainder operator and the sign of the result is the sign of the dividend. When truncation is done towards minus infinity, % is a modulo operator and the sign of the result is the sign of the divisor.

On the reasons why C changed the implementation defined behavior of the integer division regarding truncation, Doug Gwyn from C comittee said:

C99 imposed a Fortran-compatible requirement in an attempt to attract more Fortran rogrammers and to aid in converting Fortran code to C.

C99 Rationale says regarding truncation towards zero integer division:

In Fortran, however, the result will always truncate toward zero, and the overhead seems to be acceptable to the numeric programming community. Therefore, C99 now requires similar behavior, which should facilitate porting of code from Fortran to C.

In gcc the implementation behavior in C89 has always been the truncation towards zero.

So % is the remainder operator in C99, C++ and also in Java but is not the remainder operator in all programming languages. In Ruby and Python, % is in fact the modulo operator (integer division is done towards minus infinity in these languages). Haskhell and Scheme have two separate operators: mod and rem for Haskell, and modulo and remainder for Scheme.

回答3:

I'm afraid that the problem arises from a misunderstanding of mathematics. Congruence modulo n is an equivalence relation, so it only defines equivalence classes. Hence, it's not correct to say that 'in math, the answer really should be 9' because it could be as well 19, 29, and so forth. And of course it can be -1 or -11. There are infinite elements of the class of the numbers n that are n ≡ -1 mod(10).

http://en.wikipedia.org/wiki/Modular_arithmetic

http://en.wikipedia.org/wiki/Congruence_relation

So, the correct question could be: which element of the class of the numbers that are ≡ -1 mod(10) will be the result of -1 % 10 in C++? And the answer is: the remainder of the division of -1 by 10. No mystery.

PS Your definition of modulus and Knuth's are, ehm, equivalent...:)