欧博abgpython - Perhitungan cepat bilangan Fibonacci_欧博ABG官网-欧博官方网址-会员登入

python - Perhitungan cepat bilangan Fibonacci umum ke-N dengan urutan K?

Bagaimana saya bisa menghitung suku ke-N dalam deret Fibonacci orde K secara efisien?

Sebagai contoh, Tribonacci adalah Fibonacci urutan ke-3, Tetranacci adalah Fibonacci urutan ke-4, Pentanacci adalah Fibonacci urutan ke-5, dan Hexanacci adalah Fibonacci urutan ke-6 dan seterusnya.

Saya mendefinisikan deret ini sebagai berikut, untuk urutan K, A0=1, Ai=2i-1 (i ∈ [1, k]), Ak+1=2k - 1, Ai+1=2Ai - Ai-k-1 (i >= k + 1).

Sebagai contoh, urutan Fibonacci hingga Nonanacci adalah:

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040] [1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425] [1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533, 28074040, 54114452, 104308960] [1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096, 786568, 1546352, 3040048, 5976577, 11749641, 23099186, 45411804, 89277256, 175514464] [1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109, 29970, 59448, 117920, 233904, 463968, 920319, 1825529, 3621088, 7182728, 14247536, 28261168, 56058368, 111196417, 220567305] [1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776, 987568, 1967200, 3918592, 7805695, 15548665, 30972384, 61695880, 122895984, 244804400] [1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128, 32192, 64256, 128257, 256005, 510994, 1019960, 2035872, 4063664, 8111200, 16190208, 32316160, 64504063, 128752121, 256993248] [1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, 518145, 1035269, 2068498, 4132920, 8257696, 16499120, 32965728, 65866496, 131603200, 262947072]

Sekarang, saya benar-benar sadar tentang algoritma cepat untuk menghitung bilangan Fibonacci ke-N dari orde 2:

def fibonacci_fast(n: int) -> int: a, b = 0, 1 bit = 1 << (n.bit_length() - 1) if n else 0 while bit: a2 = a * a a, b = 2 * a * b + a2, b * b + a2 if n & bit: a, b = a + b, a bit >>= 1 return a def matrix_mult_quad( a: int, b: int, c: int, d: int, e: int, f: int, g: int, h: int ) -> tuple[int, int, int, int]: return ( a * e + b * g, a * f + b * h, c * e + d * g, c * f + d * h, ) def fibonacci_binet(n: int) -> int: a, b = 1, 1 bit = 1 << (n.bit_length() - 2) if n else 0 while bit: a, b = (a * a + 5 * b * b) >> 1, a * b if n & bit: a, b = (a + 5 * b) >> 1, (a + b) >> 1 bit >>= 1 return b def fibonacci_matrix(n: int) -> int: if not n: return 0 a, b, c, d = 1, 0, 0, 1 e, f, g, h = 1, 1, 1, 0 n -= 1 while n: if n & 1: a, b, c, d = matrix_mult_quad(a, b, c, d, e, f, g, h) e, f, g, h = matrix_mult_quad(e, f, g, h, e, f, g, h) n >>= 1 return a In [591]: %timeit fibonacci_matrix(16384) 751 μs ± 4.74 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) In [592]: %timeit fibonacci_binet(16384) 132 μs ± 305 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each) In [593]: %timeit fibonacci_fast(16384) 114 μs ± 966 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Tapi ini tentu saja hanya berlaku untuk deret Fibonacci-2, mereka tidak bisa digunakan untuk menghitung suku ke-N pada deret Fibonacci dengan urutan lebih tinggi.

Secara khusus, hanya persamaan kubik untuk Tribonacci: x3 - x2 - x - 1=0 dan persamaan kuartik untuk Tetranacci: x4 - x3 - x2 - x - 1=0 yang memiliki solusi yang dapat ditemukan secara aljabar, persamaan kuintik x5 - x4 - x3 - x2 - x - 1=0 memiliki solusi yang tidak dapat ditemukan dengan sympy, sehingga metode penggandaan cepat hanya bekerja pada Fibonacci, Tribonacci, dan Tetranacci.

Tapi saya tahu dua cara untuk menghitung urutan Fibonacci tingkat tinggi, yang pertama dapat digunakan untuk menghasilkan semua N bilangan Fibonacci pertama dari urutan K secara efisien dan memiliki kompleksitas waktu O(n), yang kedua adalah perpangkatan matriks dengan metode kuadrat dan memiliki kompleksitas waktu O(log2n) * O(k3).

Pertama, kita hanya membutuhkan dua angka untuk mendapatkan bilangan Fibonacci berikutnya dari orde K, persamaannya diberikan di atas, kita hanya memerlukan satu pergeseran kiri dan satu pengurangan untuk setiap suku.

Matrix = list[int] def onacci_fast(n: int, order: int) -> Matrix: if n <= order + 1: return [1] + [1 << i for i in range(n - 1)] last = n - 1 result = [1] + [1 << i for i in range(order + 1)] + [0] * (last - order - 1) result[start := order + 1] -= 1 for a, b in zip(range(start, last), range(1, last - order)): result[a + 1] = (result[a] << 1) - result[b] return result ONACCI_MATRICES = {} IDENTITIES = {} def onacci_matrix(n: int) -> Matrix: if matrix := ONACCI_MATRICES.get(n): return matrix mat = [1] * n + [0] * (n * (n - 1)) for i in range(1, n): mat[i * n + i - 1] = 1 ONACCI_MATRICES[n] = mat return mat def onacci_pow(n: int, k: int) -> np.ndarray: base = np.zeros((k, k), dtype=np.uint64) base[0] = 1 for i in range(1, k): base[i, i - 1] = 1 prod = np.zeros((k, k), dtype=np.uint64) for i in range(k): prod[i, i] = 1 return [(prod := prod @ base) for _ in range(n)] def identity_matrix(n: int) -> Matrix: if matrix := IDENTITIES.get(n): return matrix result = [0] * n**2 for i in range(n): result[i * n + i] = 1 IDENTITIES[n] = result return result def mat_mult(mat_1: Matrix, mat_2: Matrix, side: int) -> Matrix: # sourcery skip: use-itertools-product result = [0] * (square := side**2) for y in range(0, square, side): for x in range(side): e = mat_1[y + x] for z in range(side): result[y + z] += mat_2[x * side + z] * e return result def mat_pow(matrix: Matrix, power: int, n: int) -> Matrix: result = identity_matrix(n) while power: if power & 1: result = mat_mult(result, matrix, n) matrix = mat_mult(matrix, matrix, n) power >>= 1 return result def onacci_nth(n: int, k: int) -> int: return mat_pow(onacci_matrix(k), n, k)[0] In [621]: %timeit onacci_nth(16384, 2) 822 μs ± 5.88 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each) In [622]: %timeit onacci_fast(16384, 2) 13.8 ms ± 92.7 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [623]: %timeit onacci_fast(16384, 3) 16 ms ± 63.6 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [624]: %timeit onacci_fast(16384, 4) 17 ms ± 66.5 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [625]: %timeit onacci_nth(16384, 3) 4.02 ms ± 32 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [626]: %timeit onacci_nth(16384, 4) 10.9 ms ± 71 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [627]: %timeit onacci_nth(16384, 5) 22.5 ms ± 632 μs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [628]: %timeit onacci_nth(16384, 6) 39.4 ms ± 314 μs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [629]: %timeit onacci_fast(16384, 6) 17.5 ms ± 27.2 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [630]: %timeit onacci_fast(16384, 7) 17.6 ms ± 115 μs per loop (mean ± std. dev. of 7 runs, 100 loops each) In [631]: %timeit onacci_nth(16384, 7) 62.7 ms ± 347 μs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [632]: %timeit onacci_nth(32768, 16) 2.29 s ± 5.78 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) In [633]: %timeit onacci_fast(32768, 16) 56.2 ms ± 271 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Dalam kasus yang paling mudah, onacci_nth(16384, 2) secara signifikan lebih lambat daripada fibonacci_matrix meskipun menggunakan metode yang sama persis, karena adanya overhead tambahan dari penggunaan list. Dan meskipun loop while memiliki log2n iterasi, matriks memiliki ukuran k2 dan untuk setiap sel harus dilakukan k perkalian dan k - 1 penjumlahan, sehingga total k3 perkalian dan k3 - k2 penjumlahan di setiap iterasi. Biaya ini meningkat sangat cepat, sehingga metode perkalian matriks dikalahkan dengan cepat oleh metode iterasi linier, karena meskipun metode iterasi memiliki lebih banyak iterasi, setiap iterasi jauh lebih murah.

Perpangkatan matriks menggunakan seluruh matriks k*k tetapi kita membutuhkan lebih sedikit angka. Berikut adalah transisi keadaan untuk Hexanacci:

[array([[1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0]], dtype=uint64), array([[2, 2, 2, 2, 2, 1], [1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0]], dtype=uint64), array([[4, 4, 4, 4, 3, 2], [2, 2, 2, 2, 2, 1], [1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0]], dtype=uint64), array([[8, 8, 8, 7, 6, 4], [4, 4, 4, 4, 3, 2], [2, 2, 2, 2, 2, 1], [1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0]], dtype=uint64), array([[16, 16, 15, 14, 12, 8], [ 8, 8, 8, 7, 6, 4], [ 4, 4, 4, 4, 3, 2], [ 2, 2, 2, 2, 2, 1], [ 1, 1, 1, 1, 1, 1], [ 1, 0, 0, 0, 0, 0]], dtype=uint64), array([[32, 31, 30, 28, 24, 16], [16, 16, 15, 14, 12, 8], [ 8, 8, 8, 7, 6, 4], [ 4, 4, 4, 4, 3, 2], [ 2, 2, 2, 2, 2, 1], [ 1, 1, 1, 1, 1, 1]], dtype=uint64), array([[63, 62, 60, 56, 48, 32], [32, 31, 30, 28, 24, 16], [16, 16, 15, 14, 12, 8], [ 8, 8, 8, 7, 6, 4], [ 4, 4, 4, 4, 3, 2], [ 2, 2, 2, 2, 2, 1]], dtype=uint64), array([[125, 123, 119, 111, 95, 63], [ 63, 62, 60, 56, 48, 32], [ 32, 31, 30, 28, 24, 16], [ 16, 16, 15, 14, 12, 8], [ 8, 8, 8, 7, 6, 4], [ 4, 4, 4, 4, 3, 2]], dtype=uint64), array([[248, 244, 236, 220, 188, 125], [125, 123, 119, 111, 95, 63], [ 63, 62, 60, 56, 48, 32], [ 32, 31, 30, 28, 24, 16], [ 16, 16, 15, 14, 12, 8], [ 8, 8, 8, 7, 6, 4]], dtype=uint64), array([[492, 484, 468, 436, 373, 248], [248, 244, 236, 220, 188, 125], [125, 123, 119, 111, 95, 63], [ 63, 62, 60, 56, 48, 32], [ 32, 31, 30, 28, 24, 16], [ 16, 16, 15, 14, 12, 8]], dtype=uint64)]

Sekarang, untuk setiap keadaan, kita bisa menggeser baris ke bawah sebanyak 1 untuk mendapatkan k - 1 baris bawah dari keadaan berikutnya, dan baris atas bisa didapatkan dengan menambahkan angka pertama ke angka kedua dan meletakkannya di posisi pertama, menambahkan angka pertama ke angka ketiga dan meletakkannya di posisi kedua, menambahkan angka pertama ke angka keempat dan meletakkannya di posisi ketiga... meletakkan angka pertama di posisi terakhir.

Atau dalam Python:

def next_onacci(arr: np.ndarray) -> np.ndarray: a = arr[0, 0] return np.concatenate([[[a + b for b in arr[0, 1:]] + [a]], arr[:-1]])

Jadi kita hanya memerlukan k angka untuk mendapatkan kondisi berikutnya. Tapi kita bisa melakukan lebih baik, suku ke-N ditemukan dengan menaikkan matriks ke pangkat N dan mengakses mat[0, 0]. Kita bisa menggunakan mat[0, 0] + mat[0, 1] untuk mendapatkan mat[0, 0] berikutnya, atau kita bisa menggunakan 2 * mat[0, 0] - mat[-1, -1].

Tapi saya hanya menemukan cara untuk menghitung angka menggunakan hubungan ini secara linear, saya tidak bisa menggunakannya untuk melakukan perpangkatan dengan kuadrat.

Apakah ada cara yang lebih cepat untuk menghitung suku ke-N dari deret Fibonacci orde tinggi?

Tentu saja onacci_pow meluap dengan sangat cepat, jadi sama sekali tidak berguna untuk menghitung suku untuk N yang besar. Dan karena itu saya tidak menggunakannya untuk menghitung suku untuk N yang besar. Saya telah mengimplementasikan perkalian matriks dan pemangkatan sendiri untuk menghitung dengan presisi tak terbatas.

onacci_pow digunakan untuk memverifikasi kebenaran perkalian matriks saya untuk N yang kecil. onacci_pow benar selama tidak terjadi overflow, dan saya mengetahui dengan tepat pada pangkat berapa itu terjadi overflow.

Dan untuk nilai N dan K, anggap K berada antara 25 dan 100, dan N berada antara 16384 dan 1048576.

Jawaban #1

Ya, ada cara yang lebih cepat untuk menghitung ini.

Diagonaliasi Matriks

Eksponensiasi matriks dapat dioptimalkan jika matriks tersebut diagonalizable.

Ternyata matriks tersebut dapat didiagonalisasi. Memang, kita tahu bahwa matriks Fibonacci orde n M adalah matriks bujur sangkar dan semua baris serta kolomnya saling bebas linear (menurut desain). Ini berarti pangkat matriks adalah n (yaitu matriks dengan pangkat penuh). Berikut adalah penjelasan alternatif yang (lebih kompleks): teorema Spektral menyatakan bahwa matriks normal dapat didiagonalisasi oleh basis ortonormal dari vektor-vektor eigen. Karena kita dapat membuktikan bahwa M @ M.T sama dengan M.T @ M, maka M adalah matriks normal dan dapat didiagonalisasi.

Ini berarti M=Q @ L @ inv(Q) di mana Q berisi vektor-vektor eigen (satu per kolom) dan L adalah matriks diagonal yang berisi nilai-nilai eigen (satu pada setiap elemen diagonal) (lihat dekomposisi nilai singular, alias SVD, dan dekomposisi eigen dari sebuah matriks untuk informasi lebih lanjut). Kita tahu bahwa semua nilai eigen bukan nol karena matriks ini memiliki peringkat penuh.

Kita dapat menghitung itu di Numpy dengan L, Q=np.linalg.eig(M). Perlu dicatat bahwa nilai eigen dan vektor eigen dapat mengandung bilangan kompleks. Kita dapat memeriksa bahwa semuanya sejauh ini bekerja sesuai harapan dengan:

D = np.diag(L) P = np.linalg.inv(Q) T = Q @ D @ P np.allclose(M, T)

Sekarang kita dapat menghitung Mⁿ lebih efisien dibandingkan dengan eksponen kuadrat. Memang:

Mⁿ = (Q D P)ⁿ = (Q D P) (Q D P) (Q D P) ... (Q D P) = Q D (P Q) D (P Q) D (P ... Q) D P = Q D I D I D (I ... I) D P since P @ Q = I = Q D D D ... D P = Q Dⁿ P

Q @ Dⁿ @ P dapat dihitung dalam O(k log n + k³). Memang, Dⁿ sebenarnya sama dengan D**n (perpangkatan elemen demi elemen) di Numpy karena D adalah matriks diagonal. Bahkan, kita dapat menghitung Mⁿ=Q @ Dⁿ @ P dengan:

Dn = np.diag(L**n) P = np.linalg.inv(Q) Mn = Q @ Dn @ P

Metode ini secara asimtotik sekitar O(k²) kali lebih cepat daripada O(k³ log n). Sebenarnya, untuk angka floating-point (FP) berukuran tetap, ini dilakukan dalam waktu O(k³)!

Sayangnya, angka FP dengan ukuran tetap jelas tidak begitu akurat untuk angka besar, terutama untuk perhitungan Fibonacci orde tinggi (misalnya melakukan perhitungan SVD dari matriks besar). Metode ini dapat dianggap sebagai aproksimasi yang sangat baik untuk parameter yang Anda gunakan untuk k < 100. Namun demikian, perhitungan L**n gagal untuk nilai n > 16384 (sebenarnya bahkan untuk nilai n yang jauh lebih kecil). Hal ini terutama berlaku ketika L mengandung bilangan kompleks. Anda dapat menulis dekomposisi eigen dari matriks dengan angka FP berukuran besar secara arbitrer (misalnya menggunakan paket decimal), meskipun ini merepotkan untuk ditulis dan kinerja kode pasti jauh dari optimal (meskipun algoritmanya efisien). Sympy dan mpmath mungkin dapat membantu untuk itu.

Catatan tentang angka besar sewenang-wenang

Mengingat angka FP/angka bulat yang sangat besar, saya memperkirakan perhitungan suku Fibonacci ke-n akan lebih mahal dari yang diperkirakan sebelumnya. Memang, sejauh yang saya tahu, F(n) adalah angka yang memiliki O(n) bit! Ini berarti metode di atas sebenarnya O(n) lebih mahal dengan angka sebesar itu jika operasi dasar dilakukan dalam waktu O(n). Ini berlaku untuk penjumlahan tetapi tidak untuk perkalian. Perkalian angka besar bawaan CPython menggunakan algoritma Karatsuba yang berjalan sekitar O(n**1.6) waktu, sedangkan decimal. Decimal menggunakan algoritma Number Theoretic Transform yang tampaknya berjalan dalam waktu O(n log n) (terima kasih kepada @KellyBundy yang telah menunjukkannya). Kompleksitas optimal untuk perkalian bilangan n-bit adalah O(n log n). Sampai kalimat ini, saya akan mengasumsikan algoritma O(n log n) digunakan untuk mengalikan bilangan dengan ukuran sembarang (misalnya kode yang menggunakan decimal.Decimal). Faktanya, ini juga berlaku untuk algoritma lain yang disediakan dalam pertanyaan: kamu melewatkan fakta bahwa bilangan bisa sangat besar!

Mengingat hal tersebut, algoritme di atas seharusnya berjalan dalam O(k n log² n + n k³) dengan bilangan FP yang sewenang-wenang besar dan mempertimbangkan waktu perkalian O(n log n) (untuk bilangan n-bit).

Meningkatkan algoritma berbasis diagonal

Untungnya, kita tidak perlu menghitung seluruh matriks Mn=Q @ Dn @ P tetapi hanya satu elemen saja. Kita bisa mengganti perkalian matriks terakhir dengan produk titik sederhana. Dengan demikian, kita hanya memerlukan satu kolom dari P dan satu baris dari Q @ Dn. Yang terakhir dapat dihitung lebih efisien karena Dn adalah matriks diagonal:

Mn[i, j] = np.dot(Q[i] * L**n, P[:,j]) = np.sum(Q[i] * L**n * P[:,j]) = np.sum(Q[i] * P[:,j] * L**n)

Meskipun kita bisa menghitung Q[i] * P[:,j] secara efisien terlepas dari n, kita tentu membutuhkan presisi yang sangat baik untuk perhitungan ini karena L**n sangat besar untuk nilai n yang relatif besar.

Versi ini seharusnya masih berjalan dalam O(k log n + k³) untuk angka berukuran tetap (L**n adalah bagian yang mahal) dan seharusnya berjalan dalam O(k n log² n) untuk angka FP yang sangat besar.

Saya pikir kompleksitas dari algoritma terbaik (menggunakan bilangan bulat besar sembarangan) adalah Ω(k n) karena Fibonacci urutan-k membutuhkan k suku dengan presisi n-bit. Ini mengasumsikan bahwa sukunya tidak sepele. Dengan asumsi itu, ini berarti algoritma ini sebenarnya sudah cukup bagus.

Kemungkinan optimisasi lebih lanjut

Salah satu cara untuk lebih meningkatkan algoritma berbasis diagonalisation mungkin adalah dengan menghitung secara aljabar istilah matriks Fibonacci orde-k (biasanya menggunakan sympy dengan asumsi bahwa itu cukup kuat). Anda mungkin melihat beberapa istilah saling membatalkan atau beberapa pola yang memungkinkan optimisasi lebih lanjut. Anda dapat menemukan contoh di sini untuk Fibonacci klasik (dengan matriks 2x2). Saya tidak terlalu optimis karena solusi aljabar orde-2 yang ditemukan mengandung 2 istilah yang tidak dapat direduksi, jadi saya memperkirakan setidaknya k istilah dengan Fibonacci orde-k. Selain itu, saya pikir solusi algoritmik yang ditemukan kurang stabil secara numerik dibandingkan pendekatan di atas karena pembatalan katastrofik (yaitu ϕⁿ−ψⁿ).

(责任编辑：)

搜索

热门标签:

欧博abgpython - Perhitungan cepat bilangan Fibonacci