我正在嘗試實作一個代碼，用于檢索百萬分之一的斐波那契數或更多。我將矩陣乘法與 Numpy 一起使用以進行更快的計算。
根據我的理解，它應該花費 O(logN) 時間，最壞的情況是一百萬應該導致：接近 6 秒，這應該沒問題。
以下是我的實作：
def fib(n):
import numpy as np
matrix = np.matrix([[1, 1], [1, 0]]) ** abs(n)
if n%2 == 0 and n < 0:
return -matrix[0,1]
return matrix[0, 1]
但是，留下 100 萬，它甚至不會為 1000 生成正確的回應
實際反應：
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
我的回復：
817770325994397771
為什么 Python 通常會從檔案中截斷回應，它甚至應該能夠計算 10**1000 個值。我哪里做錯了？
uj5u.com熱心網友回復：
Numpy 可以以高性能的方式處理數字和計算（記憶體效率和計算時間）。因此，雖然 Python 可以處理足夠大的數字，但 Numpy 不能。你可以讓 Python 做計算并得到結果，換取性能下降。
示例代碼：
import numpy as np
def fib(n):
# the difference is dtype=object, it will let python do the calculation
matrix = np.matrix([[1, 1], [1, 0]], dtype=object) ** abs(n)
if n%2 == 0 and n < 0:
return -matrix[0,1]
return matrix[0, 1]
print(fib(1000))
輸出：
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
PS：警告
百萬分之一斐波那契數非常大，您應該確保 Python 可以處理它。如果沒有，您將不得不實作/找到一些模塊來處理這些大數字。
uj5u.com熱心網友回復：
我不相信 numpy 在這里有多大幫助，因為它不直接支持 Python 在矢量化操作中的非常大的整數。O(logN) 演算法的基本 Python 實作在我的筆記本電腦上在 0.15 秒內獲得了第 100 萬個斐波那契數。迭代（慢）方法在 12 秒內得到它。：
def slowfibo(N):
a = 0
b = 1
for _ in range(1,N): a,b = b,a b
return a
# Nth Fibonacci number (exponential iterations) O(log(N)) time (N>=0)
def fastFibo(N):
a,b = 1,1
f0,f1 = 0,1
r,s = (1,1) if N&1 else (0,1)
N //=2
while N > 0:
a,b = f0*a f1*b, f0*b f1*(a b)
f0,f1 = b-a,a
if N&1: r,s = f0*r f1*s, f0*s f1*(r s)
N //= 2
return r
輸出：
f1K = slowFibo(1000) # 0.00009 sec
f1K = fib(1000) # 0.00011 sec (tandat's)
f1K = fastFibo(1000) # 0.00002 sec
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
f1M = slowFibo(1_000_000) # 12.52 sec
f1M = fib(1_000_000) # 0.2769 sec (tandat's)
f1M = fastFibo(1_000_000) # 0.14718 sec
19532821287077577316...68996526838242546875
len(str(f1M)) # 208988 digits
uj5u.com熱心網友回復：
你的功能的核心是
np.matrix([[1, 1], [1, 0]]) ** abs(n)
這是在維基文章中討論的
np.matrix實作**as __pwr__，而后者又使用np.linalg.matrix_power. 本質上，這是一個重復的dot矩陣乘法，通過按 2 的冪對乘積進行分組來適度增強。
In [319]: M=np.matrix([[1, 1], [1, 0]])
In [320]: M**10
Out[320]:
matrix([[89, 55],
[55, 34]])
np.matrix不鼓勵使用，所以我可以用
In [321]: A = np.array(M)
In [322]: A
Out[322]:
array([[1, 1],
[1, 0]])
In [323]: np.linalg.matrix_power(A,10)
Out[323]:
array([[89, 55],
[55, 34]])
使用（新）@矩陣乘法運算子，這與：
In [324]: A@A@A@A@A@A@A@A@A@A
Out[324]:
array([[89, 55],
[55, 34]])
matrix_power 更像是：
In [325]: A2=A@A; A4=A2@A2; A8=A4@A4; A8@A2
Out[325]:
array([[89, 55],
[55, 34]])
還有一些比較時間：
In [326]: timeit np.linalg.matrix_power(A,10)
16.2 μs ± 58.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [327]: timeit M**10
33.5 μs ± 38.8 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [328]: timeit A@A@A@A@A@A@A@A@A@A
25.6 μs ± 914 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [329]: timeit A2=A@A; A4=A2@A2; A8=A4@A4; A8@A2
10.2 μs ± 97.9 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
numpy整數在int64, in處實作c，因此大小有限。因此，我們得到適度的 100 溢位：
In [330]: np.linalg.matrix_power(A,100)
Out[330]:
array([[ 1298777728820984005, 3736710778780434371],
[ 3736710778780434371, -2437933049959450366]])
我們可以通過將 dtype 更改為object. 這些值是 Python 整數，并且可以無限增長：
In [331]: Ao = A.astype(object)
In [332]: Ao
Out[332]:
array([[1, 1],
[1, 0]], dtype=object)
幸運的是matrix_power可以干凈地處理objectdtype：
In [333]: np.linalg.matrix_power(Ao,100)
Out[333]:
array([[573147844013817084101, 354224848179261915075],
[354224848179261915075, 218922995834555169026]], dtype=object)
通常物件 dtype 上的數學運算較慢，但在這種情況下不是：
In [334]: timeit np.linalg.matrix_power(Ao,10)
14.9 μs ± 198 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
我猜這是因為陣列的大小（2,2）很小，快速編譯的方法沒有用。這基本上是一個迭代任務，numpy沒有任何優勢。
縮放還不錯 - 增加n10，但時間只會增加 3-4 倍。
In [337]: np.linalg.matrix_power(Ao,1000)
Out[337]:
array([[70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501,
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875],
[43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875,
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626]],
dtype=object)
In [338]: timeit np.linalg.matrix_power(Ao,1000)
53.8 μs ± 83 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
使用物件資料型別np.matrix：
In [340]: Mo = M.astype(object)
In [344]: timeit Mo**1000
86.1 μs ± 164 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
對于百萬，時間并不像我預期的那么糟糕：
In [352]: timeit np.linalg.matrix_power(Ao,1_000_000)
423 ms ± 1.92 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
為了比較，fastFibo我機器上的時間是：
In [354]: fastFibo(100)
Out[354]: 354224848179261915075
In [355]: timeit fastFibo(100)
3.91 μs ± 154 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [356]: timeit fastFibo(1000)
9.37 μs ± 23.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [357]: timeit fastFibo(1_000_000)
226 ms ± 12.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/401967.html