Fast Fibonacci的速度超过1,000,000

Question

我通过快速加倍使用从矩阵求幂算法得到的算法编写了一个非常标准的斐波纳契函数,该算法应该在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,但它仍然在最后停止.

为什么这个大整数的速度会停止？

Answer 1

尝试像这样运行代码

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

问题是这fib(1000000)是一个非常大的数字(> 10 ²⁰⁰⁰⁰⁰).您的计算机可以非常快速地对这些数字进行操作,因为所有内容都以二进制形

当您尝试显示数字时,需要将其转换为基数10.这可能非常耗时!

转换为十六进制更容易.这些位只需要分为四个,所以

print hex(res)

将很快开始吐出东西