Algoritma yang efisien untuk menghitung angka Fibonacci

11

Angka Fibonacci dapat dihitung dalam waktu linier menggunakan pengulangan berikut: $n$

def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

Angka Fibonacci juga dapat dihitung sebagai $n$ . Namun, ini memiliki masalah dengan masalah pembulatan bahkan untukrelatif kecil. Mungkin ada beberapacara untuk mengatasi initetapi saya lebih suka tidak melakukannya. $\left[\varphi^n / \sqrt{5}\right]$ $n$

Apakah ada algoritma (logaritmik dalam nilai atau lebih baik) yang efisien untuk menghitung angka Fibonacci ke- yang tidak bergantung pada aritmatika floating point? Asumsikan bahwa operasi integer ( , , , ) dapat dilakukan dalam waktu yang konstan. $n$ $n$ $+$ $-$ $\times$ $/$

algorithms time-complexity recurrence-relation augurar
sumber

5

Sebagai saran, artikel Wikipedia tentang angka Fibonacci memiliki banyak metode.

Nama samaran

lih. stackoverflow.com/questions/14661633/… dan tautan di dalamnya dan di sekitar.

Will Ness

14

Anda dapat menggunakan powering matriks dan identitas Dalam model perhitungan Anda, ini adalah algoritma jika Anda menggunakan kuadrat berulang untuk mengimplementasikan powering.

{[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{n} = [\begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{matrix}] .

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.$

O (\log n)

$O(\log n)$

Yuval Filmus
sumber

1

Ini klasik.

dfeuer

8

Anda juga dapat menggunakan identitas ini untuk mendapatkan perulangan

dan

.

F_{2 n - 1} = F_{n}^{2} + F_{n - 1}^{2}

$F_{2n-1} = F_n^2 + F_{n-1}^2$

F_{2 n} = F_{n}^{2} + 2 F_{n - 1} F_{n}

$F_{2n} = F_n^2 + 2F_{n-1}F_n$

augurar

4

Anda dapat membaca artikel matematika ini: Algoritme cepat untuk menghitung angka Fibonacci besar (Daisuke Takahashi): PDF .

Lebih sederhana, saya menerapkan beberapa algoritma Fibonacci di C ++ (tanpa dan dengan GMP) dan Python. Sumber lengkap tentang Bitbucket. Dari halaman utama Anda juga dapat mengikuti tautan ke:

Dokumentasi online C ++ HTML.
Sebuah dokumen matematika kecil: Angka-angka Fibonacci - beberapa hubungan untuk mengimplementasikan algoritma yang baik

Rumus yang paling berguna adalah:

$F_{2n} = F^2_{n + 1} - F^2_{n - 1} = 2 F_n F_{n - 1} + F^2_n$
$F_{2n + 1} = F^2_{n + 1} + F^2_n$

Hati-hati dengan algoritma. Anda tidak harus menghitung nilai yang sama beberapa kali. Algoritma rekursif sederhana (dengan Python):

def fibonacci_pair(n):
    """Return (F_{n-1}, F_n)"""
    if n != 0:
        f_k_1, f_k = fibonacci_pair(n//2)  # F_{k-1},F_k with k = n/2

        return ((f_k**2 + f_k_1**2,
                 ((f_k*f_k_1)*2) + f_k**2) if n & 1 == 0  # even
                else (((f_k*f_k_1)*2) + f_k**2,
                      (f_k + f_k_1)**2 + f_k**2))
    else:
        return (1, 0)

$O(\log n)$

Olivier Pirson
sumber

2

Selamat datang di Ilmu Komputer . Bisakah Anda menambahkan lebih banyak informasi ke jawaban Anda? Saat ini, tidak lebih dari dua tautan, jadi jawaban Anda akan menjadi tidak berarti jika tautan tersebut mati atau server yang digunakan tidak tersedia. Tautan ke lebih banyak informasi baik-baik saja tetapi tautan di sini adalah satu-satunya informasi. Juga, harap dicatat bahwa pertanyaannya sangat jelas tentang algoritma, bukan tentang implementasi C ++. Implementasi cenderung mengaburkan algoritma di balik perincian khusus bahasa.

David Richerby

David, tautan pertama adalah tautan ke artikel matematika. Judul Algoritme cepat [...] menjawab pertanyaan "Apakah ada algoritma yang efisien (logaritmik pada nilai n atau lebih baik) [...]?" Tautan kedua adalah tautan ke berbagai implementasi saya, dalam C ++ dan Python, dan sebuah dokumen matematika kecil dengan beberapa rumus.

Olivier Pirson

2

Tidak, judul artikel, yang berisi jawaban Anda, tidak menjawab apa pun. The teks dari artikel, yang jawaban Anda mengandung hampir tidak ada, suara seperti itu mungkin tidak menjawab pertanyaan itu. Tetapi Stack Exchange adalah situs tanya jawab, bukan link farm. (Dan, tidak, saya tidak menyarankan Anda menyalin-tempel artikel itu ke dalam jawaban Anda. Tetapi ringkasan dibutuhkan.)

David Richerby

Jika Anda ingin ringkasan, tulislah!

Olivier Pirson

0

$O(\log_2 n)$

Periksa buku gratis Matters Computational dan kode pari / gp.

joro
sumber

5

Lebih baik merangkum ide-ide daripada hanya memposting tautan.

augurar

Algoritma yang efisien untuk menghitung angka Fibonacci

Jawaban: