Wydajny algorytm do obliczania tej liczby Fibonacciego

11

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$ $+$ $-$ $\times$ $/$

algorithms time-complexity recurrence-relation augurar
źródło

5

Jako sugestię, artykuł z Wikipedii na temat liczb Fibonacciego zawiera wiele metod.

pseudonim

por. stackoverflow.com/questions/14661633/… i linki tam i wokół.

Czy Ness

14

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

{[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{n} = [\begin{matrix} {fa}_{n + 1} & {fa}_{n} \\ {fa}_{n} & {fa}_{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
źródło

1

To klasyk.

dfeuer

8

Tej tożsamości można także użyć do uzyskania nawrotów

i

.

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$

sierpień

4

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

Olivier Pirson
źródło

2

Witamy w informatyce . Czy możesz dodać więcej informacji do swojej odpowiedzi? W tej chwili są to tylko dwa łącza, więc Twoja odpowiedź stanie się bez znaczenia, jeśli te linki umrą lub serwery, na których są niedostępne. Linki do dodatkowych informacji są w porządku, ale linki tutaj są jedynymi informacjami. Pamiętaj również, że pytanie dotyczy zdecydowanie algorytmów, a nie implementacji C ++. Implementacje zwykle zaciemniają algorytmy kryjące się za szczegółami specyficznymi dla języka.

David Richerby

David, pierwszy link to link do artykułu matematycznego. Tytuł Szybki algorytm [...] odpowiada na pytanie „Czy istnieje skuteczny (logarytmiczny w wartości n lub lepszej) algorytm [...]?” Drugi link to link do moich różnych implementacji w C ++ i Python oraz mały dokument matematyczny z kilkoma formułami.

Olivier Pirson

2

Nie, tytuł artykułu, który zawiera twoją odpowiedź, nic nie odpowiada. Tekst artykułu, która odpowiedź zawiera prawie żaden, brzmi jak to prawdopodobnie ma odpowiedzieć na pytanie. Ale Stack Exchange to strona pytań i odpowiedzi, a nie farma linków. (I nie, nie sugeruję, abyś skopiował i

wkleił

Jeśli chcesz podsumować, napisz je!

Olivier Pirson

0

$O(\log_2 n)$

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

joro
źródło

5

Lepiej streścić pomysły, a nie tylko zamieszczać linki.

sierpień

Wydajny algorytm do obliczania tej liczby Fibonacciego

Odpowiedzi: