快速斐波納契慢如蝸牛超過1,000,000

我寫的利用應爲O運行（日誌（n））的通話時間和矩陣冪算法得出的算法通過快速增加一倍相當標準的斐波那契功能，但攤上了大約超過1,000,000 - 即使這應該只是大約25個電話。快速斐波納契慢如蝸牛超過1,000,000

代碼：

""" 
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)

此代碼應該僅產生的log（n）調用fib_helper和一個呼叫斐波那契數。對於大於1,000,000的數字，它只是停頓而不返回。

我試圖實現一個基本的裝飾來計算函數調用它告訴我，它僅運行32呼籲2^32，但它仍然在最後攤出來。

這是爲什麼要放緩大整數停止？

來源

2013-10-31 reem

嘗試運行你喜歡這個

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

的問題是，fib(1000000)是一個相當大的數字（> 10 ）代碼。您的計算機可以快速操作這些數字，因爲一切都是以二進制完成的。

當您嘗試顯示數字時，需要將其轉換爲基數10.這可能非常耗時！

轉換爲十六進制是容易得多。該位只需要被分成四肢着地，所以

print hex(res)

將開始吐東西出來很快

來源

2013-10-31 03:33:12

嘗試使用'decimal。十進制「並將小數精度設置爲」非常大「。然後輸出轉換時間將變得微不足道（十進制數字的線性） - CPython binary-> decimal轉換時間是位數的二次方。 –

如果數量變大，即使計算部分運行速度太慢。在我的電腦上，fib（10,000,000）需要永遠運行。 – satoru

@ Satoru.Logic，在這臺計算機上'fib（1000000）'需要不到100ms –

只是爲了興趣，因爲我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中，在C中實現了decimal，並且計算時間與使用本機（二進制）整數相當。但點是輸出轉換爲十進制字符串的時間：它不是一個巨大的瓶頸，它成爲運行時的一個微不足道的部分。

例如，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個多萬元十進制數字的字符串。對於參數十億，大約0.9秒產生208,987,640位十進制字符串：十進制數字顯然是線性的。

注意：decimal實際上是針對在十進制浮點和定點計算。雖然它可以用於高精度整數計算，但您必須提前指定需要的位數和最大指數。它沒有「無界」模式。以上代碼使用fibonacci(n)約等於1.618**n。

來源

2013-10-31 05:23:45

快速斐波納契慢如蝸牛超過1,000,000

回答

相關問題