4
votes

$5.6/4 in C++03 states- "If both operands are nonnegative then the remainder is nonnegative;if not, the sign of the remainder is implementation-defined74).

where Note 74 is

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

C++0x states -

$5.6/4- "For integral operands the / operator yields the algebraic quotient with any fractional part discarded;79 if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.

Note 79 says

This is often called truncation towards zero.

So I have two questions:

  • Can someone explain this concept of 'truncation towards zero'?

  • Is modulus with negative operands a defined behavior in C++0x?

3
Alas, the new definition still doesn't have the basic modulo property that is most often wanted: A mod B should be guaranteed to produce a value between 0 and B, including 0 but excluding B.swestrup
@swestrup: it's all about priorities. If you require A%B ∈ [0,B), and you also require (A/B)*B + A%B == A, then A/B must have a perverse rounding rule viz. truncate towards -∞. 10/-3 == -4 under such rounding, and (-A)/B != -(A/B).Philip Potter
@Philip Potter: In this case 'truncation' and 'rounding', do they mean the same?Chubsdad
chubsdad: good question! Here I'm using "rounding" to mean "any scheme for converting a real to an integer by discarding information" and I use truncation to mean "rounding by always going in a fixed direction, towards zero or -inf". Another rounding scheme is "nearest integer": where 2.3 -> 2 and 2.7 -> 3. This rounding scheme is not a truncation - nor is it commonly used in integer divide operations in programming languages. My usage is probably not standard, but I hope this clarifies my comment.Philip Potter
Yes, but this 'perverse' rounding scheme is the one that is the one that is needed in the vast majority of cases when working with signed integers. I've yet to see any use cases that show the current definition to be very useful. In fact, its usually justified by being hardware efficient, and that's because the hardware gets it wrong too. Perl's modulo operator gets it right, unless one uses integer mode...swestrup

3 Answers

6
votes

Truncation towards zero means converting a real number to an integer by selecting the next integer nearest zero. Equivalently, you write the number down, and ignore everything after the decimal point, whether the number is positive or negative.

Consider 11/4 = 2.75 -- if you truncate this towards zero, you get 2.

consider -11/4 or 11/-4 = -2.75 -- if you truncate this towards zero, you get -2.

It's important for some maths operations that (a/b)*b + a%b == a. If we must make this equation hold, and we also accept that integer division truncates towards zero, then we can deduce the operation of the % operator as follows:

a == 11, b == 4:
a/b == 2, 2*4 + a%b == 11, therefore a%b == 3.

a == -11, b == 4:
a/b == -2, -2 * 4 + a%b == -11, therefore a%b == -3.

a == 11, b == -4:
a/b == -2, -2 * -4 + a%b == 11, therefore a%b == 3.

a == -11, b == -4:
a/b == 2, 2 * -4 + a%b == -11, therefore a%b == -3.

It might be confusing at first, but C++0x is defining the behaviour of the a%b operator using the equation (a/b)*b + a%b == a. This equation holds even for negative numbers, so a%b is defined for negative numbers.

3
votes

a) Consider (±5)/(±3) -> ±1. On the number line:

  (-5)/3                                     5/3
     5/(-3)                               (-5)/(-3)
      =                                       =
    -1.66 --> -1                       1 <-- 1.66
       v       v                       v       v
-  +  -  -  -  +  -  -  -  +  -  -  -  +  -  -  -  +  -
   |           |           |           |           |
  -2          -1           0           1           2

the rounding is thus towards zero.

b) Yes. Since a/b is now defined for all a and b (except b == 0), and (a/b)*b + a%b == a, there is only 1 unique solution for a%b, so the % operator is also well-defiend for all a and b (except b == 0).

1
votes

a) "Truncation towards zero" simply means that any decimal part is lopped off. The truncated number is always at least as close to 0 as, and usually closer than, the original number.

This is most noticeable in negative numbers, but the goal is to make it less tricky to use / and % with negative numbers (since currently, any implementation can handle it however they choose). -7/4 can be thought of two ways: -2 with a remainder of 1, or -1 with a remainder of -3. And there are compilers and processors that handle it both ways. Since -7/4 is actually -1.75, "truncation toward zero" would give you -1, so the latter way is what'll be standard.

b) That's what it looks like. It's always been semi-defined ("implementation-defined"), but this looks like an attempt to define what should have been standard from the beginning.