c++ – Is a > c / b a safer equivalent (but avoiding overflow) version of a * b > c for positive integer division?
This came up in a C++ program I am writing for iterating over a loop, where it was pointed out that the for loop condition a * b > c could overflow. I am rusty with integer math but I think, mathematically ignoring overflow, a * b > c is equivalent to a > c // b, so the second form can be used to avoid overflow in C++ code. For the sake of clarity, I will use the python syntax of / means rational division and // means integer division:
- Forward: a * b > c implies a > c / b >= c // b. (by defn of floor. Same for a * b >= c)
- Backwards: a * b <= c implies a <= c / b < (c // b) + 1, so I think it must be that a <= c // b. (For integers, a <= b iff a < b + 1.) By contrapositive, a > c // b implies a * b > c.
Is this correct? The definition of floor I use is for any real x, floor(x) is the integer satisfying floor(x) <= x < floor(x) + 1.
The same question applies for whether a * b >= c is equivalent to a >= c // b. The forward argument I think holds, but backwards fails for a=2, b=2, c=5, since 2 >= 5 // 2 but NOT 2 * 2 >= 5 as Mark Glisse points out in the comments. In that case, how can a * b >= c be safely tested without overflow?
Read more here: Source link
