4

我已经使用从矩阵求幂算法派生的算法快速加倍编写了一个非常标准的斐波那契函数，该算法应该在 O(log(n)) 时间和调用中运行，但在超过 1,000,000 时停止 - 即使这应该只是大约 25 个电话。

代码：

"""
O(log(n)) time fibonacci algorithm using fast doubling derived from the matrix
squaring algorithm for the same thing.
"""

def fibonacci(num):
    "O(log(n)) implementation of fibonacci using fast doubling."
    if num >= 0:
        return fib_helper(num)[0]

def fib_helper(num):
    "Helper function for fibonacci()."
    if num == 0:
        return (0, 1)
    elif num == 1:
        return (1, 1)
    else:
        f_k, f_k_1 = fib_helper(num // 2)
        f_k_even = f_k * (2 * f_k_1 - f_k)
        f_k_odd = f_k_1 * f_k_1 + f_k * f_k
        return (f_k_even, f_k_odd) if num % 2 == 0 else (f_k_odd, f_k_even +
                f_k_odd)

此代码应仅生成对 fib_helper 的 log(n) 调用和对 fibonacci 的一次调用。对于大于 1,000,000 的数字，它只会停止并且不会返回。

我已经尝试实现一个基本的装饰器来计算函数调用，它告诉我它只运行 32 次调用 2^32，但它最终仍然停滞不前。

为什么这会在大整数上停止？

4

2 回答 2

9

尝试像这样运行你的代码

print "calculating fib(1000000)"
res = fib(1000000)
print "displaying the result..."
print res

问题是这fib(1000000)是一个相当大的数字（> 10 200000）。您的计算机可以非常快速地对这些数字进行操作，因为一切都是以二进制形式完成的。

当您尝试显示数字时，需要将其转换为以 10 为基数。这可能非常耗时！

转换为十六进制要容易得多。这些位只需要分成四组，所以

print hex(res)

会很快开始吐出东西

于 2013-10-31T03:33:12.443 回答
3

只是出于兴趣，因为我的decimal评论显然难以理解;--)，这里是代码：

import decimal
from decimal import Decimal as D
DO = D(0)
D1 = D(1)

def fibonacci(num):
    from math import log10
    if num >= 0:
        ndigits = int(log10(1.62) * num + 100)
        decimal.getcontext().prec = ndigits
        decimal.getcontext().Emax = ndigits
        return fib_helper(num)[0]

def fib_helper(num):
    if num == 0:
        return (D0, D1)
    elif num == 1:
        return (D1, D1)

其余部分fib_helper()不变（请参阅原始消息）。在 Python 3 中，decimal是用 C 实现的，计算时间与使用本机（二进制）整数相当。但关键是输出转换为十进制字符串的时间：它不是一个巨大的瓶颈，而是运行时的一个微不足道的部分。

例如，fibonacci(100000000)（一亿）在这个盒子上大约需要 30 秒，但在那之后：

>>> from time import clock as now # on this box, `clock()` is wall-clock time
>>> if 1:
...    t = now()
...    print(len(str(x)))
...    print(now()-t)
...
20898764
0.10466078789343337

因此需要十分之一秒才能生成 20+ 百万个十进制数字的字符串。对于参数 10 亿，生成 208,987,640 位十进制字符串大约需要 0.9 秒：十进制位数明显呈线性关系。

注意：decimal实际上是针对十进制浮点和定点计算。虽然它可以很好地用于高精度整数计算，但您必须提前指定所需的位数和最大指数。它没有“无界”模式。上面的代码使用fibonacci(n)大约等于1.618**n.

于 2013-10-31T05:23:45.633 回答