使用整数除法时，将 "a/(b*c)" 替换为 "a/b/c" 是否安全？

Question

在正整数上使用整数除法 a,b,c 时，将 a/(b*c) 替换为 a/b/c 是否安全，或者我是否有丢失信息的风险？

我做了一些随机测试，但找不到 a/(b*c) != a/b/c 的示例，所以我很确定它是安全的，但不太确定如何证明它。

谢谢。

Answer 1

只要您跟踪除数和被除数，就可以对嵌套的楼层除法重新排序。

#python3.x
x // m // n = x // (m * n)

#python2.x
x / m / n = x / (m * n)

证明（没有 LaTeX 很烂 :( ) 在 python3.x:

Let k = x // m
then k - 1 < x / m <= k
and (k - 1) / n < x / (m * n) <= k / n

In addition, (x // m) // n = k // n
and because x // m <= x / m and (x // m) // n <= (x / m) // n
k // n <= x // (m * n)

Now, if k // n < x // (m * n)
then k / n < x / (m * n)
and this contradicts the above statement that x / (m * n) <= k / n

so if k // n <= x // (m * n) and k // n !< x // (m * n)
then k // n = x // (m * n)

and (x // m) // n = x // (m * n)

https://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Nested_divisions

Answer 2

虽然 b*c 对于原始计算可能会溢出（在 C 中），但 a/b/c 不会溢出，因此我们无需担心前向替换的溢出 a/(b*c) -> a/b/c.不过，我们需要反过来担心它。

让x = a/b/c。然后 a/b == x*c + y 一些 y < c，a == (x*c + y)*b + z 一些 z < b。

因此，a == x*b*c + y*b + z。 y*b + z 最多是 b*c-1，所以 x*b*c <= a <= (x+1)*b*c，a/(b*c) == x。

因此，a/b/c == a/(b*c)，将 a/(b*c) 替换为 a/b/c 是安全的。

Answer 3

数学

作为数学表达式，⌊a/(bc)⌋ 和 ⌊⌊a/b⌋/c⌋ 等价于 b 非零且 c 是正整数（特别是正整数 a、b、c）。这类事情的标准参考是 Graham、Knuth 和 Patashnik 合着的 Concrete Mathematics: A Foundation for Computer Science 这本令人愉快的书。其中，第 3 章主要介绍地板和天花板，这在第 71 页作为更一般结果的一部分得到证明：

在上面的3.10中，你可以定义x = a/b（数学，即实数除法）和f(x) = x/c（再次精确除法），并将它们插入左边的结果⌊f(x)⌋ = ⌊f(⌊x⌋)⌋（在验证 f 上的条件在这里成立之后）使左轴上的 ⌊a/(bc)⌋ 等于右轴上的 ⌊⌊a/b⌋/c⌋。

如果我们不想依赖书本上的参考，我们可以直接用他们的方法证明⌊a/(bc)⌋ = ⌊⌊a/b⌋/c⌋。请注意，对于 x = a/b（实数），我们要证明的是 ⌊x/c⌋ = ⌊⌊x⌋/c⌋。所以：

如果x是一个整数，那么就没有什么需要证明的了，因为x = ⌊x⌋.
否则⌊x⌋ < x，所以⌊x⌋/c < x/c也就是⌊⌊x⌋/c⌋ ≤ ⌊x/c⌋。（我们想证明它是相等的。）为了矛盾起见，假设 ⌊⌊x⌋/c⌋ < ⌊x/c⌋ 那么一定有一个数 y 使得 ⌊x⌋ < y ≤ x 和 y/c = ⌊x/c⌋。（当我们将数字从 ⌊x⌋ 增加到 x 并考虑除以 c 时，我们必须在某处达到确切的值 ⌊x/c⌋。）但这意味着 y = c*⌊x/c⌋是⌊x⌋和x之间的整数，矛盾！

这证明了结果。

编程

#include <stdio.h>

int main() {
  unsigned int a = 142857;
  unsigned int b = 65537;
  unsigned int c = 65537;

  printf("a/(b*c) = %d\n", a/(b*c));
  printf("a/b/c = %d\n", a/b/c);
}

打印（32 位整数），

a/(b*c) = 1
a/b/c = 0

（我使用无符号整数，因为它们的溢出行为是 well-defined，所以上面的输出是有保证的。对于有符号整数，溢出是未定义的行为，所以程序实际上可以打印（或做）任何东西，这只会强化结果可能不同的观点。）

但是如果你没有溢出，那么你在程序中得到的值就等于它们的数学值（即你代码中的a/(b*c)等于数学值⌊a/(bc)⌋，并且代码中的a/b/c等于数学值⌊⌊a/b⌋/c⌋），我们已经证明它们是相等的。因此当 b*c 足够小不会溢出时，用 a/b/c 替换代码中的 a/(b*c) 是安全的。

使用整数除法时，将 "a/(b*c)" 替换为 "a/b/c" 是否安全？

Is it safe to replace "a/(b*c)" with "a/b/c" when using integer-division?

language-agnostic

math

integer-division

数学

编程