即使最终值适合,计算如何导致算术溢出?

计算科学 算法 数值限制
2021-12-23 20:52:32

我正在阅读Skiena 的算法设计手册,它在第 8 章第 8.1.4 节谈到二项式系数的计算时说:

中间计算很容易导致算术溢出,即使最终系数恰好适合整数。

我想不出一个理由。两者之间的任何计算不应该总是小于最终结果吗?

2个回答

二项式系数的问题在于它们是阶乘的商,它可能相当大,特别是比最终的二项式系数大得多:

(nk)=n!k!(nk)!

例如,(105)=25210!=3628800(分子)。在另一个例子中(1005)=75287520因此可以表示为一个正则整数,而100!10158不能表示为整数。

因此,在计算二项式系数时,只计算通常是不明智的n!k!(nk)!并将两者分开,因为您的计算机可能无法处理n!. 相反,您需要考虑不包含大量数字作为中间结果的方法,例如:

(nk)=i=1kn+1ii

在这里,每个因素都是一个相对较小的整数,没有中间结果大于最终结果。

即使这样,二项式系数也可能很容易变得非常大(甚至超出浮点数的限制)并且可能只是中间结果本身。因此,您可能需要求助于计算对数域中的所有内容并使用阶乘的近似值,例如斯特林的大多数数学库都loggamma为此目的提供了一个函数,它返回log(Γ(n))=log((n1)!). (另一方面,许多数学库也提供了二项式系数的合理实现。)

即使最终结果没有溢出,中间结果也可能溢出。有一些方法可以重新安排一个方程,这样就不会发生这种情况,但这取决于程序员(也许一个优化编译器也是定理求解器也可以做到 - 但我从未见过)并且 CPU 赢了'不要自己重新排序算术指令序列。

而不是试图在理论上证明它,我只会提供一个至少发生一个实例的简单例子:

为简单起见,假设一台 8 位机器:

int8 a = 10
int8 b = 30
int8 c

c = (a * b) / 2

最终结果是 150。它适合 8 位寄存器。但是中间结果(a * b)是 30 x 10,即 300,它不适合 8 位寄存器,因此会溢出。

由于溢出,如果要在 8 位机器上运行上述计算,结果将是令人惊讶的 22 而不是 150(300 mod 256 是 44 和 44/2 = 22)。