替换"a/(b * c)"是否安全?与"a/b/c"一起使用什么时候使用整数除法? [英] Is it safe to replace "a/(b*c)" with "a/b/c" when using integer-division?

问题描述

在正整数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 on positive integers a,b,c, or am I at risk losing information?

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

I did some random tests and couldn't find an example of a/(b*c) != a/b/c, so I'm pretty sure it's safe but not quite sure how to prove it.

谢谢.

推荐答案

数学

作为数学表达式，每当b为非零且c为正整数(尤其是对于正整数a，b，c)时，⌊a/(bc)⌋和⌊⌊a/b⌋/c⌋等价.这类事情的标准参考书是Graham，Knuth和Patashnik撰写的令人愉快的《具体数学:计算机科学的基础》一书.在其中，第3章主要是在地板和天花板上，这在第71页上得到了证明，它是更为通用的结果的一部分:

Mathematics

As mathematical expressions, ⌊a/(bc)⌋ and ⌊⌊a/b⌋/c⌋ are equivalent whenever b is nonzero and c is a positive integer (and in particular for positive integers a, b, c). The standard reference for these sorts of things is the delightful book Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth and Patashnik. In it, Chapter 3 is mostly on floors and ceilings, and this is proved on page 71 as a part of a far more general result:

在上述3.10中，您可以定义x = a/b(数学的即实数除法)和f(x) = x/c(再次精确除法)，然后将其插入左侧⌊f(x)⌋ = ⌊f(⌊x⌋)⌋的结果中(确认条件在f上按住)以在LHS上获得⌊a/(bc)⌋，在RHS上等于⌊⌊a/b⌋/c⌋.

In the 3.10 above, you can define x = a/b (mathematical, i.e. real division), and f(x) = x/c (exact division again), and plug those into the result on the left ⌊f(x)⌋ = ⌊f(⌊x⌋)⌋ (after verifying that the conditions on f hold here) to get ⌊a/(bc)⌋ on the LHS equal to ⌊⌊a/b⌋/c⌋ on the RHS.

如果我们不想依赖一本书中的参考文献，则可以直接使用它们的方法证明⌊a/(bc)⌋ = ⌊⌊a/b⌋/c⌋.请注意，对于x = a/b(实数)，我们试图证明的是⌊x/c⌋ = ⌊⌊x⌋/c⌋.所以:

If we don't want to rely on a reference in a book, we can prove ⌊a/(bc)⌋ = ⌊⌊a/b⌋/c⌋ directly using their methods. Note that with x = a/b (the real number), what we're trying to prove is that ⌊x/c⌋ = ⌊⌊x⌋/c⌋. So:

• 如果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⌋和<之间的整数c20>，这是一个矛盾！

• if x is an integer, then there is nothing to prove, as x = ⌊x⌋.
• Otherwise, ⌊x⌋ < x, so ⌊x⌋/c < x/c which means that ⌊⌊x⌋/c⌋ ≤ ⌊x/c⌋. (We want to show it's equal.) Suppose, for the sake of contradiction, that ⌊⌊x⌋/c⌋ < ⌊x/c⌋ then there must be a number y such that ⌊x⌋ < y ≤ x and y/c = ⌊x/c⌋. (As we increase a number from ⌊x⌋ to x and consider division by c, somewhere we must hit the exact value ⌊x/c⌋.) But this means that y = c*⌊x/c⌋ is an integer between ⌊x⌋ and x, which is a contradiction!

这证明了结果.

#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位整数)

prints (with 32-bit integers),

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

(我使用无符号整数作为溢出行为，因为它们是

(I used unsigned integers as overflow behaviour for them is well-defined, so the above output is guaranteed. With signed integers, overflow is undefined behaviour, so the program can in fact print (or do) anything, which only reinforces the point that the results can be different.)

但是，如果没有溢出，则程序中获得的值等于它们的数学值(即，代码中的a/(b*c)等于数学值⌊a/(bc)⌋和a/b/c在代码中等于数学值⌊⌊a/b⌋/c⌋)，我们已经证明它是相等的.因此，当b*c足够小而不会溢出时，可以安全地用a/b/c替换代码中的a/(b*c).

But if you don't have overflow, then the values you get in your program are equal to their mathematical values (that is, a/(b*c) in your code is equal to the mathematical value ⌊a/(bc)⌋, and a/b/c in code is equal to the mathematical value ⌊⌊a/b⌋/c⌋), which we've proved are equal. So it is safe to replace a/(b*c) in code by a/b/c when b*c is small enough not to overflow.

这篇关于替换"a/(b * c)"是否安全?与"a/b/c"一起使用什么时候使用整数除法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！