8

可能重复：
在 Python 中处理非常大的数字

我有一个 python 函数来生成斐波那契数：

def fib(n):                                                                                                            
        return ((1+math.sqrt(5))**n - (1-math.sqrt(5))**n)/(2**n*math.sqrt(5))

我可以提供高达 700 的 fib 函数编号，从那里开始

OverflowError: (34, 'Numerical result out of range')

我需要使用像 long 这样的特殊类型来解决这个问题吗？

4

4 回答 4

10

问题是您使用双打来计算值并且双打溢出。双打只给出了大约第 85 个斐波那契数的精确解。

如果您想要快速准确的计算，最好使用基于更好递归关系的算法，并使用 python bignum 整数。

特别是您可以使用：

 fib(2*n) = fib(n)^2 + fib(n-1)^2
 fib(2*n-1) = fib(n)*(2*fib(n-1)+fib(n))

或等效的矩阵求幂公式（请原谅丑陋的格式）

 [ F_n     F_{n-1} ]      [ 1   1 ] ^N 
 [                 ]  =   [       ]
 [ F_{n-1} F_{n-2} ]      [ 1   0 ]

这两种方法都导致算法需要O(log(N))计算而不是O(N).

这是伪代码的完整解决方案

如果您确实想使用双精度数和显式公式执行计算，那么可以调整公式以提供更快的结果，直到大约第 1500 个斐波那契数时才会溢出，并且与您的版本保持相同的准确性。IIRC 它是：

def fib(n):                                                                                                            
    return round( ((1+math.sqrt(5))/2)**n / math.sqrt(5) )
于 2012-10-01T02:17:38.180 回答
4

很容易隔离错误

>>> (1+math.sqrt(5))**700
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: (34, 'Numerical result out of range')

此方法效果不佳，因为浮点数没有足够的精度

例如，这里

>>> (1+math.sqrt(5))**600
1.024664165563927e+306

您只使用前 15 位左右的数字。当您进行任何算术运算时，剩余的 291 将被视为零

有关浮点数的准确性问题的更多信息，请参见维基百科

于 2012-10-01T01:39:02.133 回答
4

您可以随时尝试这种方法：

def fib(n, memo={0:0, 1:1}):
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print fib(800)

输出：

69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725

于 2012-10-01T01:43:52.353 回答
2

如果你真的想使用那个算法，并且你想超越内置的限制float，那么是的，你需要一个不同的类型。

如果您只想得到一个近似答案而不是异常，那很容易；您可以开箱即用地获得无限范围。但是，如果您还想消除舍入误差，则不能具有无限的精度（这将花费无限的时间/空间），因此您必须知道如何计算输入范围所需的精度。（我将把它作为练习留给读者。）

标准库类型decimal.Decimal可能就是您所需要的。它根据 IEEE-854 标准提供任意精度的定点或浮点十进制算法。在很多情况下它是不可用的，因为它没有提供足够的数学函数，但你只需要基本的算术和sqrt，就可以了。对于大数字来说，它也可能很慢，但如果你只想计算fib几个三位数，那就绰绰有余了。

不足时Decimal，还有很多第三方模块，通常封装了行业标准的 C 库，如 gmp/mpfr，如bigfloat。

以下是如何获得无限范围，但舍入误差与内置浮点数大致相同：

>>> s5 = decimal.Decimal(5).sqrt()
>>> def fib(n):
...     return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
Decimal('6.928308186422471713629008226E+166')
>>> int(fib(800))
69283081864224717136290082260000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
>>> s5 = bigfloat.sqrt(5)
>>> def fib(n):
...     return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
BigFloat.exact('6.9283081864226567e+166', precision=53)
>>> int(fib(800))
69283081864226566841137772774650010139572747244991592044952506898599601083170460360533811597710072779197410943266632999194601974766803264653830633103719677469311107072L

但是请注意，如果您完美地完成了数学运算，这些实际上都不是您得到的答案；您因舍入错误而丢失了 24 位数字。（值不同的原因是以bigfloat2 为底，以 10 为底四舍五入decimal。）

要解决这个问题，您需要更高的精度。所有库都提供了一些改变精度的方法；bigfloat有比大多数更方便的选择，但没有一个太繁琐：

>>> decimal.getcontext().prec = 300
>>> s5 = decimal.Decimal(5).sqrt()
>>> def fib(n):
...     return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fib(800)
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000048
>>> def fibp(n, p):
...     with bigfloat.precision(p):
...         s5 = bigfloat.sqrt(5)
...         return ((1+s5)**n - (1-s5)**n)/(2**n*s5)
>>> fibp(800, 125)
BigFloat.exact('6.92830818642247171362900776814484912138e+166', precision=125)
>>> int(fibp(800, 125))
69283081864224717136290077681448491213794574774712670552070914552025662674717073354503451578576268674564384721027806323979200718479461097490537109958812524476157132800L
于 2012-10-01T04:18:51.200 回答