我正在阅读Skiena 的算法设计手册,它在第 8 章第 8.1.4 节谈到二项式系数的计算时说:
中间计算很容易导致算术溢出,即使最终系数恰好适合整数。
我想不出一个理由。两者之间的任何计算不应该总是小于最终结果吗?
我正在阅读Skiena 的算法设计手册,它在第 8 章第 8.1.4 节谈到二项式系数的计算时说:
中间计算很容易导致算术溢出,即使最终系数恰好适合整数。
我想不出一个理由。两者之间的任何计算不应该总是小于最终结果吗?
二项式系数的问题在于它们是阶乘的商,它可能相当大,特别是比最终的二项式系数大得多:
例如,但(分子)。在另一个例子中因此可以表示为一个正则整数,而不能表示为整数。
因此,在计算二项式系数时,只计算通常是不明智的和并将两者分开,因为您的计算机可能无法处理. 相反,您需要考虑不包含大量数字作为中间结果的方法,例如:
在这里,每个因素都是一个相对较小的整数,没有中间结果大于最终结果。
即使这样,二项式系数也可能很容易变得非常大(甚至超出浮点数的限制)并且可能只是中间结果本身。因此,您可能需要求助于计算对数域中的所有内容并使用阶乘的近似值,例如斯特林的。大多数数学库都loggamma为此目的提供了一个函数,它返回. (另一方面,许多数学库也提供了二项式系数的合理实现。)
即使最终结果没有溢出,中间结果也可能溢出。有一些方法可以重新安排一个方程,这样就不会发生这种情况,但这取决于程序员(也许一个优化编译器也是定理求解器也可以做到 - 但我从未见过)并且 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)。