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

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

prob 变得非常大并最终溢出。鉴于名称，您是否打算 prob 始终介于 0 和 1 之间？

Answer 2

你的 prob 变量变得非常大，当总数等于 4964 时它会溢出 Python 最大浮点值 sys.float_info

>>> import sys
>>> print(sys.float_info.max)
1.7976931348623157e+308

Answer 3

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

如果您准备好接受（相当小的）浮点数错误，则根本不需要使用循环来计算此数量：您可以使用 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 项，并且只在最后一刻（除以 4**count 时）产生浮点数。这将比上面的效率低，但会给你（在某种意义上）完美的准确性，因为它会给准确答案最接近的可表示浮点数。这是该版本的样子：

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中的底数除法可能看起来不对，但它确实有效：一点初等数论表明，在计算的这一点上，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 的解决方案更准确。

Answer 4

你是什么意思"controlled calculation"？溢出的原因是prob越来越大

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

Why am I getting inf on controlled calculation?

python

cpython