Wydajny algorytm do obliczania tej liczby Fibonacciego

p liczbę Fibonacciego można obliczyć w czasie liniowej stosując następujący nawrotu:$n$

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

p liczbę Fibonacciego może być obliczana jako . Ma to jednak problemy z zaokrąglaniem nawet dla stosunkowo niewielkiej . Prawdopodobnie są na to sposoby, ale wolałbym tego nie robić.$n$$\left[\varphi^n / \sqrt{5}\right]$$n$

Czy istnieje wydajny (logarytmiczny w wartości lub lepszej) algorytm do obliczania tej liczby Fibonacciego, który nie opiera się na arytmetyki zmiennoprzecinkowej? Załóżmy, że operacje na liczbach całkowitych ( , , , ) mogą być wykonywane w stałym czasie.n + - × $n$$n$$+$$-$$\times$$/$

Możesz użyć zasilania macierzy i tożsamości W twoim modelu obliczeniowym jest to algorytm O ( log n ) , jeśli używasz powtarzającego się kwadratu, aby zaimplementować zasilanie.

Możesz przeczytać ten artykuł matematyczny: Szybki algorytm obliczania dużych liczb Fibonacciego (Daisuke Takahashi): PDF .

Mówiąc prościej, zaimplementowałem kilka algorytmów Fibonacciego w C ++ (bez GMP iz GMP) oraz w Pythonie. Kompletne źródła na Bitbucket. Na stronie głównej możesz również przejść do linków do:

• Dokumentacja online C ++ HTML.
• Mały dokument matematyczny: liczby Fibonacciego - kilka relacji do wdrożenia dobrych algorytmów

Najbardziej przydatne formuły to:

• $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$

Uważaj na algorytm. Nie wolno obliczać tej samej wartości kilka razy. Prosty algorytm rekurencyjny (w języku 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)

Jego złożoność jest logarytmiczna (jeśli podstawowe operacje odbywają się w stałym czasie): .$O(\log n)$

$O(\log_2 n)$

Sprawdź bezpłatną książkę Matters Computational i kod pari / gp.