Fibonacci序列中可能出现非常大的数字错误（python2.7.6 integer math）

Question

编辑后以粗体显示问题。

我编写了以下Python代码（使用python2.7.6）来计算Fibonacci序列。它不使用任何额外的库，只使用核心python模块。在

我在想，我能计算的序列中的项是否有限制，也许是因为得到的整数长度太长，或者Python是否不再精确地执行计算。

另外，对于fibott（n）函数，它似乎有时返回请求项下的项（例如，第99项而不是第100项），但总是在较低的项（第1项、第2项、第10项、第15项）下工作。为什么？

def fibopt(n): # Returns term "n" of the Fibonacci sequence.
    f = [0,1] # List containing the first two numbers in the Fibonacci sequence.
    x = 0 # Empty integer to store the next value in the sequence. Not really necessary.
    optnum = 2 # Number of calculated entries in the sequence. Starts at 2 (0, 1).
    while optnum < n: # Until the "n"th value in the sequence has been calculated.
        if optnum % 10000 == 0:
            print "Calculating index number %s." % optnum # Notify the user for every 10000th value calculated. This is useful because the program can take a very long time to calculate higher values (e. g. about 15 minutes on an i7-4790 for the 10000000th value).
        x = [f[-1] + f[-2]] # Calculate the next value in the sequence based of the previous two. This could be built into the next line.
        f.extend(x) # Append that value to the sequence. This could be f.extend([f[-1] + f[-2]]) instead.
        optnum +=1 # Increment the counter for number of values calculated by 1.
        del f[:-2] # Remove all values from the table except for the last two. Without this, the integers become so long that they fill 16 GB of RAM in seconds.
    return f[:n] # Returns the requested term of the sequence.

def fib(n): # Similar to fibopt(n), but returns all of the terms in the sequence up to and including term "n". Can use a lot of memory very quickly.
    f = [0,1]
    x = 0
    while len(f) < n:
        x = [f[-1] + f[-2]]
        f.extend(x)
    return f[:n]

Answer 1

好消息是：Python中的整数数学很简单，没有溢出。在

只要您的整数可以放入Clong，Python就会使用它。一旦你超过了这一点，它将自动升级为任意精度的整数（这意味着它将更慢，占用更多内存，但计算将保持正确）。在

唯一的限制是：

1. Python进程可寻址的内存量。如果您使用的是32位Python，那么您需要能够将所有数据放在2GB或RAM内（超过这个值，您的程序将失败，MemoryError）。如果您使用64位Python，那么您的物理RAM+swapfile是理论上的限制。

2. 在计算过程中你愿意等待的时间。整数越大，计算就越慢。如果你碰到你的交换空间，你的程序将达到大陆漂移水平的缓慢。

Answer 2

如果您阅读Python2.7文档，有一节介绍斐波纳契数。在这个关于斐波那契数的部分中，任意结尾不是我们都想看到的拉长答案。它缩短了它。在

如果这不能回答您的问题，请参阅：4.6定义函数。在

如果你已经下载了解释器，手册是预装的。如果有必要，你可以上网www.python.org或者您可以查看手册，查看以“任意”短结尾的Fibonacci数，即不是整个数值。在

赛斯

另外，如果您对手册中的这一部分有任何疑问，请参阅Python教程/4。更多控制流工具/4.6定义功能。我希望这能有所帮助。在

Answer 3

Python整数可以表示任意长度的值，并且不会自动转换为float。只需创建一个非常大的数字并检查其类型即可进行检查：

>>> type(2**(2**25))
<class 'int'>  # long in Python 2.x

fibott返回f[:n]，这是一个列表。您似乎期望它返回一个术语，所以期望值（第一个注释）或实现必须更改。在