对于正整数除法，a > c / b 是 a * b > c 的更安全的等效（但避免溢出）版本吗？

Question

这出现在我正在编写的用于迭代循环的 C++ 程序中，其中指出 for 循环条件

a * b > c

可能会溢出。我对整数数学很生疏，但我认为，在数学上忽略溢出，

a * b > c

相当于

a > c // b

，所以第二种形式可以用来避免C++代码中的溢出。为了清楚起见，我将使用 Python 语法 / 表示有理除法，// 表示整数除法：

• 向前：a * b > c 意味着 a > c / b >= c // b。 （由地板的定义。a * b >= c 相同）
• 向后：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 意味着 a * b > c。

这是正确的吗？我使用的floor的定义是对于任何实数x，floor(x)是满足floor(x)的整数<= x < floor(x) + 1.

同样的问题也适用于 a * b >= c 是否等于 a >= c // b。我认为前向论证成立，但对于 a=2、b=2、c=5，后向论证失败，因为 2 >= 5 // 2 但不是 2 * 2 >= 5，正如 Mark Glisse 在评论中指出的那样。那么，如何才能安全地测试 a * b >= c 而不发生溢出呢？

Answer 1

如果您将

>

表述为“乘以

c//b

时不超过

b

的最大整数”，那么

c

的情况就很明显了。

>=

的情况可以通过简单地将其重写为

a*b > c-1

来处理，将其减少到之前的值。