Can integer division in C/C++ run into loss of precision issues?

Question

Suppose we have three integer (int, long, long long, unsigned int, etc) variables a, b, c. Normally, performing

c = a / b;

would result in truncate of fractions. However, is it possible for c to end up with an incorrect value?

I am not talking about a / b may be out of range for c's type. Rather, I am talking about how integer division is implemented in C. Does performing a / b first generate a float type intermediate result, and then the intermediate value is truncated?

If so, I wonder if loss of precision of the intermediate value can lead to an incorrect value of c. For example, suppose the precise value for a / b is 2, but somehow the intermediate result is 1.9999..., thus c will end up with an incorrect value of 1. Can such cases happen, or does integer division always result in a correct value if the expected value is in the range of c's type?

This isn't Commodore basic, integer operations are done as integers. Integer arithmetic is generally more efficient than floating-point. — Thomas Jager, Jul 29 '19 at 14:23
Integer math is done strictly with integers. In fact some processors could only do floating point math and had an attached floating point math co-processor do deal with floating point numbers. — NathanOliver, Jul 29 '19 at 14:26
@NathanOliver So can I safely assume that integer division will always lead to a correct result? — edwardliang2019, Jul 29 '19 at 14:28
You have to worry about overflow and underflow, but other than that, integer math is precise. — Robert Harvey, Jul 29 '19 at 14:28
Possible duplicate of [Integer division rounding with negatives in C++](https://stackoverflow.com/questions/319880/integer-division-rounding-with-negatives-in-c) — hyde, Jul 29 '19 at 14:29
@NathanOliver: There is no requirement from the C standard that integer operations be implemented with only integer arithmetic, just that the results be correct. An implementation could use floating-point hardware to implement integer operations as long as it gets the results right. — Eric Postpischil, Jul 29 '19 at 17:23

eerorika · Accepted Answer · 2019-07-29T14:59:29.450

6

Does performing a / b first generate a float type intermediate result

As far as the language is concerned, there are no intermediate results.

does integer division always result in a correct value if the expected value is in the range of c's type?

Yes.

edited Jul 29 '19 at 14:59

answered Jul 29 '19 at 14:32

eerorika

232,697
12
197
326

"There are no fractions in integer division", well, I think any reasonable binary division algorithm used on silicon will also produce the fraction (or remainder, which is essentially same thing as producing fractional part), and the "basic" division instruction on a CPU will also give the remainder as part of the result (SIMD instructions probably discard it). – hyde Jul 29 '19 at 14:36
@hyde There is not always a need to generate a fraction (or use some `idiv` equivalent): https://godbolt.org/z/aRaDWM - https://homepage.divms.uiowa.edu/~jones/bcd/divide.html – Max Langhof Jul 29 '19 at 14:40
@hyde Fraction is different from remainder, even if they're related concepts. Regardless, my answer is about the language. Hardware may do whatever it wants underneath, and the language implementation has to deal with it. – eerorika Jul 29 '19 at 14:41
Yeah, of course there are special cases and optimizations for any operation where you have constants (depending on a CPU, probably for any compile time constant divisor). I'm not sure if it's fair to call that general "integer division" in this context. – hyde Jul 29 '19 at 14:49
Reminder is directly the numerator part of the fractions, with a known fixed denominator (at least for positive results, CBA to think it through for negative), so it is very nearly the same thing. Anyway, I believe current C++ standard at least does use fractions to define the result of integer division, so the concept of fractions exist for C++ integer division (can't discard something which does not exist). – hyde Jul 29 '19 at 14:56
From a recent draft found with google: *"For integral operands the / operator yields the algebraic quotient with any fractional part discarded;"* – hyde Jul 29 '19 at 14:58
@hyde oh, so it apparently does. Not the wording I would have chosen; not that it matters much either way. I removed the statement from the answer. – eerorika Jul 29 '19 at 14:58
Yeah, this is just nitpicking and semantics... I just got bothered by the absolute tone of the original first point. – hyde Jul 29 '19 at 15:00

score 3 · Answer 2 · answered Jul 29 '19 at 14:28

3

Section 6.5.5 of the C11 standards states

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a;

Which means there's no way, mathematically, that you'll get wrong results.

answered Jul 29 '19 at 14:28

Federico klez Culloca

26,308
17
56
95

1

That's not actually what that says. :) – Robert Harvey Jul 29 '19 at 14:29
@RobertHarvey well, if the result was imprecise like OP asks, supposing no remainder, `(a / b) * b` would never result in `a` (since `1.99999...` is not representable, thus not being exact). Same thing if there was a reminder. Or maybe I'm just reading too much into this. – Federico klez Culloca Jul 29 '19 at 14:31
All it means is that an incorrect result must be reversible ;) – Lightness Races in Orbit Jul 29 '19 at 14:52
@LightnessRacesinOrbit ok, but "incorrect" in this case would mean "imprecise". The question was originally about loss of precision. If that was the case, wouldn't the result of `(a/b) * b` be different from `a`? I'm sure I'm missing something when two other users are telling me I'm misinterpreting this, but I can't seem to see it. – Federico klez Culloca Jul 29 '19 at 15:14
1

@FedericoklezCulloca The question is about incorrectness resulting from imprecise intermediate stages (which don't exist). All you've proven is that, if said imprecision existed, it would be symmetrical, which doesn't prove that the result in one direction is "correct" mathematically. It will be, but this quote isn't why. – Lightness Races in Orbit Jul 29 '19 at 15:48
The not-bolded part is the part which says that there cannot be any loss of precision. – Antti Haapala -- Слава Україні Jul 29 '19 at 15:58

score 2 · Answer 3 · edited Jun 20 '20 at 09:12

Suppose we have three integer (int, long, long long, unsigned int, etc) variables a, b, c. Normally, performing
c = a / b;
would result in truncate of fractions. However, is it possible for c to end up with an incorrect value? I am not talking about a / b may be out of range for c's type.

It should not be possible that for example the last digit of division be wrong, if all rules were followed otherwise. C11 6.5.5p6:

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.

i.e. the result is not "close" to but exactly the same as a / b would be algebraically, just anything following the point discarded.

That does not mean there won't be any gotchas: it is possible that the division of a / b might be mathematically not out of range for c's type yet out of range for the type used in the division itself which can cause wrong values be set in c.

Consider this example:

#include <stdio.h>
#include <inttypes.h>   

int main(void) {
    int32_t a = INT32_MIN;
    int32_t b = -1;
    int64_t c = a / b;
    printf("%" PRId64, c);
}

The result of division of INT32_MIN / -1 is representable in c, it is INT32_MAX + 1, which is positive. However on 32-bit platforms the arithmetic happens in 32 bits, and this division produces an integer overflow which causes the behaviour to be undefined. What happens on my computer is that if I compile without optimizations it aborts the program. If I compile with optimizations enabled (-O3), the compiler will resolve this calculation at compilation time, and handles the overflow in a peculiar way and produces the result -2147483648 which is negative.

Likewise, if you do this:

uint16_t a = 16;
int16_t b = -1;
int32_t result = a / b;
printf("%" PRId32 "\n", result);

the result on a 32-bit int machine is -16. If you change the type of a to uint32_t the math happens in unsigned:

uint32_t a = 16;
int16_t b = -1;
int32_t result = a / b;
printf("%" PRId32 "\n", result);

The result is of course 0. And you would get 0 from the former calculation too on a 16-bit machine.

Can integer division in C/C++ run into loss of precision issues?

3 Answers3

Linked

Related