计算可能溢出的整数运算的最安全、最有效的方法

Question

假设我们有2个常数A

i * A / B    (1)

为了简化问题，我们假设变量< code>i总是在范围< code>[INT64_MIN*B/A，INT64_MAX*B/A]内，这样算术运算(1)的最终结果不会溢出(即:< I >适合在范围< code>[INT64_MIN，INT64_MAX]内)。

此外，假设i更可能在友好范围内，范围1=[INT64_MIN/A，INT64_MAX/A]可能（不太可能）超出此范围。在第一种情况下，i*a的简单整数计算不会溢出（这就是为什么我们称范围友好的原因）；在后一种情况下，i*a的简单整数计算将溢出，导致计算（1）时出现错误结果。


什么是“最安全”和“最有效”的计算操作方法（1）（其中“最安全”意味着：保持精确性或至少是体面的精度，其中“最有效”意味着：最低平均计算时间），前提是i更有可能在友好范围1中。

目前，代码中当前实现的解决方案如下：

(int64_t)((double)A / B * i)

哪种解决方案非常安全（无溢出），但不准确（由于双有效位53位限制而导致精度损失），并且速度非常快，因为双除法（双）A/B是在编译时预计算的，只允许在运行时计算双乘法。





Answer 1

我认为您可以在溢出发生之前检测到它。在你的情况下 i * A / B，你只担心 i * A 部分，因为除法不能溢出。

您可以通过执行布尔溢出 = i 的测试来检测溢出

Answer 2

为了给这个问题提供一个量化的答案，我对不同的解决方案做了一个基准测试，作为我在这篇文章中提出的解决方案的一部分(感谢评论和回答)。< br >

当i在友好范围Range1=[INT64_MIN/A，INT64_MAX/A]i超出友好范围（但在安全范围Range2= 内）时，基准测量不同实现的计算时间。


每个实现都执行操作的“安全”（即没有溢出）计算：i*A/B（第一个实现除外，作为参考计算时间给出）。但是，某些实现可能会返回不频繁的不准确计算结果（通知其行为）。


提出的一些解决方案尚未经过测试或未在下文列出；这些解决方案是：使用__int128的解决方案（微软vc编译器不支持），但使用了升压int128_t代替；使用扩展80位long Double的解决方案（微软vc编译器不支持）；使用InfInt的解决方案（工作和测试速度太慢，无法成为一个像样的竞争对手）。


时间测量以 ps/op 为单位指定（每次操作皮秒）。基准测试平台是 Windows 7 x64 下的英特尔Q6600@3GHz，可执行组件编译为 MS vc14、x64/版本目标。下面引用的变量、常量和函数定义为：

int64_t       i;
const int64_t A     = 1234567891;
const int64_t B     = 4321987;
inline bool   in_safe_range(int64_t i) { return (INT64_MIN/A <= i) && (i <= INT64_MAX/A); }

1. （i*A/B）[reference]
iinRange1:1469 ps/op，i超出Range1：无关（溢出）

2. （（int64_t）（（双精度）i*A/B））
Range1中的i：10613 ps/op，i超出Range1的：10606 ps/op注意：整个范围Range2中很少出现不准确的结果（最大误差=1位）

3. （（int64_t）（（double）A/B*i））
Range1中的i：1073 ps/op，i超出Range1的：1071 ps/op注意：在整个Range2范围内很少出现不准确的结果（最大错误=1位）
注意：编译器可能会预计算A/B（double-code>），与以前的解决方案相比，会导致观察到的性能提升

4. <代码>（！in_safe_range（i）？（int64_t）（（双）A/B*i）：（i*A/B））
i在Range1中：2009 ps/op，i超出Range1：1606 ps/op注意：在Range1之外很少有不准确的结果（最大误差=1位）

5. （（int64_t）（（int128_t）i*A/B））
6. （（i/B）*A（i%B）*A）/B）
i范围1中：5876 ps/op，范围1外：5879 ps/op
7. <代码>（！in_safe_range（i）？（（i/B）*A（（i%B）*A）/B）：（i*A/B））
i在Range1中：1999 ps/op，i超出Range1：6135 ps/op


结论
a）如果在整个范围内可以接受轻微的计算误差，那么解（3）是最快的解，甚至比作为参考给出的直接整数计算更快
b）如果计算错误在友好范围Range1内是不可接受的，但在此范围之外是可以接受的，那么解决方案（4）是最快的
c）如果计算错误在整个范围内都不可接受，那么解决方案（7）在友好范围内的性能与解决方案（4）一样好，并且在该范围外保持相当快的速度。


Answer 3

匿名用户

如果你不能获得更好的范围，那么你最好按照iammilind的建议使用__int128。

原因是，否则你将不得不实现字到双字乘法和双字逐字除法的完整逻辑。英特尔和AMD处理器手册包含有用的信息和现成的代码，但它非常复杂，使用C/C而不是汇编程序使事情加倍复杂。

所有好的编译器都将有用的原语作为内部函数公开。微软的列表似乎不包括类似muldiv的原语，但是< code>__mul128内在函数将128位乘积的两半作为两个64位整数提供给你。在此基础上，您可以执行两位数除以一位数的长除法，其中一位“数字”将是一个64位整数(通常称为“肢”，因为比一位数字大，但仍然只是整体的一部分)。仍然非常复杂，但比使用纯C/C好得多。然而，从可移植性的角度来看，它并不比直接使用< code>__int128好。至少这样一来，编译器实现者已经为您完成了所有的艰苦工作。

如果你的应用程序域可以给你有用的边界，比如（u % d） * v不会溢出，那么你可以使用标识

(u * v) / d = (u / d) * v + ((u % d) * v) / d

其中 / 表示整数除法，只要 u 为非负数且 d 为正数（否则您可能会违反运算符 %的语义所允许的余地）。

在任何情况下，您可能都必须分离出操作数的符号并使用未签名的操作，以便找到可以利用的更多有用机制 - 或者绕过编译器的破坏，例如您提到的饱和乘法。有符号整数操作的溢出调用未定义的行为，编译器可以自由地做任何他们想做的事情。相比之下，无符号类型的溢出是明确定义的。

此外，对于无符号类型，您可以依靠像< code>s = a ( ) b(其中< code>( )可能溢出无符号加法)这样的规则，您将得到< code>s == a b或< code>s

然而，你不太可能在这条路上走得更远，因为所需的努力很快就会接近甚至超过我之前提到的实施双肢手术的努力。只有对应用程序域进行全面分析，才能提供规划/部署此类快捷方式所需的信息。在一般情况下，以及你给出的界限，你几乎不走运了。