c++ - 这个乘除函数正确吗？

Question

我试图long long在某些计算中避免 s 和整数溢出，所以我想出了下面的函数来计算(a * b) / c（由于截断整数除法，顺序很重要）。

 unsigned muldiv(unsigned a, unsigned b, unsigned c)
 {
      return a * (b / c) + (a * (b % c)) / c;
 }

是否有任何边缘情况无法按预期工作？

Answer 1

已编辑：这对于原始明显逻辑正确的值的超集是正确的。c如果>b并且可能在其他情况下，它仍然不会为您买任何东西。也许您对自己的价值观有所了解，c但这可能不会像您期望的那样有帮助。a, b,的某些组合c仍然会溢出。

编辑：假设您long long出于严格的 C++98 可移植性原因而避免使用，您可以通过提升恰好具有整数值的 to 来进行数学运算，从而获得大约 52 位的unsigned精度double。实际上，使用double数学可能比进行三个整数除法更快。

Answer 2

这在很多情况下都失败了。最明显的是 whena很大，所以a * (b % c)溢出。在这种情况下，您可以尝试交换a和b，但如果a、b和c都很大，则仍然失败。考虑具有 32 位无符号的a= = 2^25-1 和 c = 2^24。b正确的结果是 2^26-4，但两者a * (b % c)都会b * (a % c)溢出。甚至(a % c) * (b % c)会溢出。

到目前为止，解决这个问题的最简单方法通常是扩大乘法，这样您就可以获得更高精度的中间产品。如果你没有这个，你需要用更小的乘法和除法来合成它，这与实现你自己的大整数库几乎是一样的。

如果您可以保证c足够小(c-1)*(c-1)不会溢出无符号，您可以使用：

unsigned muldiv(unsigned a, unsigned b, unsigned c) {
    return (a/c)*(b/c)*c + (a%c)*(b/c) + (a/c)*(b%c) + (a%c)*(b%c)/c;
}

这实际上将为您提供所有 a 和 b 的“正确”答案 - (a * b)/c % (UINT_MAX+1)

Answer 3

为避免溢出，您必须先除法，然后再乘以某个因子。

使用的最佳因子是 c，只要 a 和 b 之一（或两者）大于 c。这就是 Chris Dodd 的功能所做的。它具有 ((a % c) * (b % c)) 的最大中间值，正如 Chris 所指出的，它小于或等于 ((c-1)*(c-1))。

如果您可能遇到 a 和 b 都小于 c 的情况，但 (a * b) 仍然可能溢出（当 c 接近字长限制时可能会出现这种情况），那么最好使用的因素是 a 2的大幂，将乘法和除法转换为移位。尝试移动一半的字长。

请注意，当您没有更长的单词可用时，使用预除法然后乘法相当于使用更长的单词。假设您不丢弃低位，而只是将它们作为另一个术语添加，那么您只是使用几个单词而不是一个更大的单词。

我让你填写代码。