这个乘除法功能是否正确？

我试图避免long long s和整数溢出在一些计算，所以我想出了以下函数来计算(a * b)/c（顺序是重要的，因为截断整数除法）。这个乘除法功能是否正确？

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

是否有任何边缘情况下，这不会按预期工作？

来源

2012-04-25 Electro

你不说*但如果它的速度我强烈怀疑任何额外DIV/MOD操作矮储蓄。 – 2012-04-25 19:16:17

我假设你已经检查过'c = 0'。 – twain249 2012-04-25 19:18:38

你没有提到你是否希望输出是一个整数或一个双精度 - 因为你正在进行除法。如果是您担心的溢出问题，那么您可以对'a'，'b'和'c'进行归一化，然后（不）对结果进行归一化。通过规范化，我的意思是分裂/乘以10的幂数。 – 2012-04-25 19:21:27

EDITED：对于原始显而易见的逻辑正确的值的超集，这是正确的。它仍然没有购买任何东西，如果c>b并可能在其他条件下。也许你对c的价值有所了解，但这可能无法达到预期的效果。 a,b,c的某些组合仍然会溢出。

编辑：假设你避免long long严格C++ 98的便携性原因，您可以通过促进你的unsigned到double s表示碰巧有整数值做数学题获得约52位精度。数学实际上可能比做三个积分更快。

来源

2012-04-25 19:19:37

如果'c> b'变成'（a * b）/ c'，因为第一项退出并且'b％c' ='b'。此外，因为这将是<'a'它不能溢出（因为'a'适合）。 – twain249 2012-04-25 19:21:35

也许，但我不确定我是否可以用'double'可靠地计算出每一个可能的'（a * b）/ c'。 – Electro 2012-04-25 19:29:27

@Electro你不能，但取决于你的'b'，'b'，'c'的分布，它可能比你原来的方法更多。如果你真的需要能够处理每一个可能的输入值，我强烈建议你只是咬紧牙关，用'long long'。 – 2012-04-25 19:49:21

这在很多情况下都失败了。最明显的是当a很大时，所以a * (b % c)溢出。在这种情况下，您可以尝试交换a和b，但如果a,b和c都很大，则仍会失败。考虑使用32位无符号的a = b = 2^25-1和c = 2^24。正确的结果是2^26-4，但a * (b % c)和b * (a % c)都会溢出。即使(a % c) * (b % c)也会溢出。

到目前为止，解决这个问题的最简单的方法是扩大乘法，以便获得更高精度的中间产品。如果你没有这些，你需要从较小的乘法和除法中综合出来，这与实现你自己的biginteger库非常相似。

如果你能机制保障是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）

来源

2012-04-25 22:14:05

为了避免溢出，您必须先进行预分频，然后乘以某个因子。

使用的最佳因子是c，只要a和b中的一个（或两者）大于c。这就是Chris Dodd的功能。它具有（（a％c）*（b％c））的最大中间值，正如克里克所确定的，它小于或等于（（c-1）*（c-1））。

如果您可能出现a和b都小于c但（a * b）仍然可能溢出的情况（这可能是c接近字大小限制的情况），那么最佳因子使用是两个大的力量，将乘法转化为转变。尝试移动字大小的一半。

请注意，使用预先分割和后乘法相当于在没有更长的单词可用时使用更长的单词。假设您不会丢弃低位，但只是将它们添加为另一个名词，那么您只需使用几个单词而不是一个较大的单词。

为什么*您避免`长long`我会让你填写的代码英寸

来源

2012-05-04 15:15:36

这个乘除法功能是否正确？

回答

相关问题