Python如何在处理大浮点数和整数时防止溢出错误

Question

我正在写一个Python程序，用来计算斐波那契数列中的数字。这是我的代码：

import math
def F(n):
    return ((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))
def fib(n):
    for i in range(n):
        print F(i)

我的代码使用这个公式来找到斐波那契数列中的第N个数字：

这个公式可以计算斐波那契数列中的很多数字，但我遇到了溢出错误。

我该如何改进这段代码，避免溢出错误呢？

注意：我使用的是Python 2.7。

Answer 1

你提到的 我该如何改进这段代码... 有点模糊，所以我理解为你想让代码更简洁：

import math
def fib(j):
    for i in [int(((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))) for n in range(j)]: print i

你可以把你两个函数合并成一个函数，并且使用列表推导式，这样就能让这个函数在一行内完成。

如果你在处理非常大的数字时，无法避免溢出错误，建议你尝试捕获这些错误，然后进行处理：

import math
def fib(j):
        try:
                for i in [int(((1+math.sqrt(5))**n-(1-math.sqrt(5))**n)/(2**n*math.sqrt(5))) for n in range(j)]: print i
        except Exception as e:
                print 'There was an error, your number was too large!'

第二个方法会先遍历所有内容，确保没有错误，如果没有错误，就会继续打印出来。

Answer 2

我不知道这样是否对你来说可以，但你可以用整数运算来计算斐波那契数，比如用递归公式（例如，F3 = F2 + F1）。

从Python 2.5开始，你可以进行任意精度的整数运算，这样几乎就解决了溢出的问题。如果你尝试计算F(10000)，那肯定会变得非常慢。

另外，可以看看decimal模块——如果我没记错的话，在Python 2.7中你可以使用它，这样你可以指定小数运算的精度——这让你可以继续使用相同的算法，只是需要用小数类型。

补充一下

你可能会忽略decimal类里有一个平方根的方法。你需要用这个方法，而不是math.sqrt()，因为你需要保持decimal类的完整精度。

另外，计算sqrt(5)是一个相对耗时的操作，最好只计算一次。

Answer 3

Python中的整数是任意精度的，这意味着如果你用一种迭代的方法来计算斐波那契数列，你可以得到准确的结果。

>>> def fib(n):
...   a = 0
...   b = 1
...   while n > 0:
...     a, b = b, a + b
...     n = n - 1
...   return a
... 
>>> fib(100)
354224848179261915075L

Python有几个可以处理多精度浮点数的库。其中，decimal模块是Python自带的，最初是为了进行财务计算而设计的。它支持sqrt()函数，所以你可以这样做：

>>> import decimal
>>> decimal.setcontext(decimal.Context(prec=40))
>>> a=decimal.Decimal(5).sqrt()
>>> a
Decimal('2.236067977499789696409173668731276235441')
>>> ((1+a)**100 - (1-a)**100)/(a*(2**100))
Decimal('354224848179261915075.0000000000000000041')

其他的库包括mpmath和gmpy2。

>>> import gmpy2
>>> gmpy2.set_context(gmpy2.context(precision=150))
>>> a=gmpy2.sqrt(5)
>>> a
mpfr('2.2360679774997896964091736687312762354406183598',150)
>>> ((1+a)**100 - (1-a)**100)/(a*(2**100))
mpfr('354224848179261915075.00000000000000000000000248',150)
>>> gmpy2.fib(100)
mpz(354224848179261915075L)

gmpy2也可以直接计算斐波那契数（如上所示）。

免责声明：我维护gmpy2这个库。