python - 为什么我要了解受控计算？

Question

我有一个带有循环的函数，在循环中我同时进行除法和乘法运算。最终答案很容易表示，运行答案也应该如此。

def tie(total):
    count = total / 2
    prob = 1.0
    for i in xrange(1, count + 1):
        i_f = float(i)
        prob *= (count + i_f) / i_f / 4
    return prob

-

tie(4962) == 0.01132634537589437

但是

tie(4964) == inf

编译器是否试图进行一些优化，以我指定的顺序以外的顺序执行算术运算，并且该顺序应该是等效的但会导致溢出？

Answer 1

您遇到问题是因为即使您的 tie 函数的最终结果在数学上应该在 0 和 1 之间，循环中的 中间 值变得非常大:对于 total = 4962，迭代中途 prob 的值是1.5e308 左右，几乎但相当大到足以溢出 Python float。对于 total = 4964，中间值确实确实溢出了一个float，并且因为inf乘以任何有限的仍然是 inf，溢出的 inf 一直传播到最终值。

如果您准备接受(相当小的) float 错误，则根本不需要使用循环来计算此数量:您可以使用 lgamma math 模块中的函数计算相关阶乘的对数。 (您也可以直接使用 gamma 函数，但这也可能会导致溢出问题。)

这是基于此的函数版本。

from math import lgamma, log, exp

def tie(total):
    count = total / 2
    return exp(lgamma(2*count + 1) - 2*lgamma(count + 1) - count*log(4))

或者，您可以使用纯整数算法(不会导致溢出)计算 2n-choose-n 项，并且只在最后一刻产生 float (除以 4**count)。这将比上面的效率低，但会给你(在某种意义上)完美的准确性，因为它会给准确答案最接近的可表示 float 。这是该版本的样子:

from __future__ import division

def tie(total):
    count = total // 2
    prod = 1
    for i in xrange(1, count+1):
        prod = prod * (count + i) // i
    return prod / 4**count

注意:prod * (count + i)//i 中的 floor 划分可能看起来不对，但它确实有效:一点点初等数论表明在计算的这一点上, prod * (count + i) 必须能被 i 整除，因此进行整数除法是安全的。

最后，为了好玩，这是计算概率的第三种方法，它在本质上与原始代码相似，但避免了溢出:值 prob 从 1.0 开始并稳步下降到最终值。

def tie(total):
    count = total // 2
    prob = 1.0
    for i in xrange(1, count+1):
        prob *= (i-0.5) / i
    return prob

除了不受溢出问题影响外，该解决方案比基于整数的解决方案更高效，并且比基于lgamma 的解决方案更准确。