复杂计算中的浮点精度

Question

为了计算加泰罗尼亚数字，我写了两个代码。One（def“Catalan”）递归工作并返回正确的Catalan数字。在

dicatalan = {} 
def catalan(n):
if n == 0:
    return 1
else: 
    res = 0
    if n not in dicatalan:
        for i in range(n):
            res += catalan(i) * catalan(n - i - 1)
        dicatalan[n] = res
return dicatalan[n]

另一个（def“catalanFormula”）应用隐式公式，但不能从n=30开始精确计算。问题源于浮点-对于k=9，程序返回“6835971.99999999”而不是“6835972”，并从这一刻开始累积错误，直到最终的错误答案。在

（打印线用于检查）

^{pr2}$

我尝试过舍入，但失败了，尝试了十进制导入，仍然没有得到正确的结果。在

我需要“catalanFormula”和“catalan”一样完美； 有什么想法吗？在

谢谢！在

Answer 1

试着分别计算分子和分母，并在最后除以它们。如果您这样做，您应该能够使用浮点使它稍微远一点。在

我确信Python有一个rational数字包。使用理性是一个更好的主意。在

Answer 2

请参阅bigfloat包。在

from bigfloat import *

setcontext(quadruple_precision)
def catalanFormula(n):
    result = BigFloat(1)
    for k in range(2, n + 1):
        result *= ((BigFloat(n) + BigFloat(k)) / BigFloat(k))
    return result

catalanFormula(30)

输出：

^{pr2}$