Error in glibc `div () code?

Question

As stated in rounding integers with negatives in C ++, "in C to C99 (i.e., C89) and in C ++ to C ++ 11 (i.e. in C ++ 98 and C ++ 03), to calculate integer division, where any of the operands is negative, the remainder sign (or, which is the same, the direction of rounding of the quotient) is determined by the implementation.

Then the standard function std::div appears, which is indicated to truncate the quotient to zero (i.e., the remainder has the same sign as the dividend (numerator)) (see, for example, this answer to the question: "What is the purpose of the library function div ()? " ).

Here is the glibc code for div() ( source ) (also quoted in Is the div function (stdlib.h) useful? "):

(Note: div_t is defined as:

 typedef struct { int quot; int rem; } div_t; 

- end of note.)

 /* Return the `div_t' representation of NUMER over DENOM. */ div_t div (numer, denom) int numer, denom; { div_t result; result.quot = numer / denom; result.rem = numer % denom; /* The ANSI standard says that |QUOT| <= |NUMER / DENOM|, where NUMER / DENOM is to be computed in infinite precision. In other words, we should always truncate the quotient towards zero, never -infinity. Machine division and remainer may work either way when one or both of NUMER or DENOM is negative. If only one is negative and QUOT has been truncated towards -infinity, REM will have the same sign as DENOM and the opposite sign of NUMER; if both are negative and QUOT has been truncated towards -infinity, REM will be positive (will have the opposite sign of NUMER). These are considered `wrong'. If both are NUM and DENOM are positive, RESULT will always be positive. This all boils down to: if NUMER >= 0, but REM < 0, we got the wrong answer. In that case, to get the right answer, add 1 to QUOT and subtract DENOM from REM. */ if (numer >= 0 && result.rem < 0) { ++result.quot; result.rem -= denom; } return result; } 

As you can see, after a large block of comments, there is a test whose purpose is to "fix" the result if the built-in division truncates in the -infinity direction instead of zero.

Now the question is:

Are there any errors in this code?

First, consider the example of calling div(42, -5) . "In mathematics" 42 / -5 is exactly -8.4 , so theoretically in C89 and C ++ 03, 42 / -5 can be either -8 (truncated) or -9 (per floor) depending on the implementation. Code reading:

• If 42 / -5 gives -8 , then 42 % -5 gives 2 (as 42 == -8 * -5 + 2 ), so the test (42 >= 0 && 2 < 0) , which is incorrect, and the above function returns -8 and 2 , optionally;
• If 42 / -5 gives -9 , then 42 % -5 gives -3 (as 42 == -9 * -5 + -3 ), so the test (42 >= 0 && -3 < 0) , which is true, therefore, the above function returns the “adjusted” -9 + 1 and -3 - -5 , i.e. -8 and 2 , if you want.

But now consider the call to div(-42, 5) (the characters are upside down):

• If -42 / 5 gives -8 , then -42 % 5 gives -2 (as -42 == -8 * 5 + -2 ), so the test (-42 >= 0 && -2 < 0) , which is incorrect, and the above function returns -8 and -2 , optionally;
• If -42 / 5 gives -9 , then -42 % 5 gives 3 (like -42 == -9 * 5 + 3 ), so the test (-42 >= 0 && 3 < 0) , which ... does not match reality! and the above function returns -9 and 3 instead of -8 and -2 !

The comment in the above code seems correct when it says that a situation requiring correction is that "REM has the opposite sign NUMER", but then it makes a huge simplification "It all comes down to: if NUMER> = 0, but REM <0, we got the wrong answer ", which seems wrong (incomplete) for me, because it omits the case " if NUMER <0, but REM> 0 " -42 and 3 in the previous example).

I can hardly believe that such an error would go unnoticed from 1992 or 1990 (apparently, someone tried to “fix” it , but this still seems wrong, because div(-42, 5) can return -10 and 8 ) ... Apparently, most implementations are truncated towards zero by default (and all of them are necessary for this, starting with C99 and C ++ 11, so the problem is "controversial" in the latest standards ¹ ), so the error will not be displayed on them, but still ... Maybe I missed something?

Thanks for any ideas.

---

¹ (Edit) Regarding "the problem is related to C ++ 11 and C99 (and newer)": accordingly, these Standards require built-in division to truncate to zero, so we do not need to adjust the result, but does this mean that the current is implementation more complicated than necessary and overly inefficient? The "big comment" is deprecated, and the if test if useless, so you should not completely remove this part?

Answer 1

As the original author of the code, I must say: “You are right. It is broken. We did not have systems that led the“ wrong path ”for testing, and I probably wrote the above too late (or earlier ...) on the day or something like that.

We have kept the new standards, and all this needs to be cleared, perhaps with a little #ifdef (and a fixed setup code) for pre-C99, if necessary.

(I also want to note that the original was not indented with GNU-style indentation :-))

Answer 2

But in this case, the number is -42, (therefore it is negative), this made the condition false automatically. In fact, if you try to execute simple code containing a function, you will see that (debugging it) the if statement:

 // false in this case, numer = -42 and result.rem = -2 if(numer >= 0 && result.rem < 0) 

Here you can see the compiled result: enter a description of the link here

I hope the answer is correct and helps you understand the error.