Effizienter Algorithmus zur Berechnung der

11

Die te Fibonacci-Zahl kann in linearer Zeit unter Verwendung der folgenden Wiederholung berechnet werden: $n$

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

Die - te Fibonacci - Zahl kann auch wie folgt berechnet werden $n$ . Dies hat jedoch Probleme mit Rundungsproblemen für selbst relativ kleine. Es gibt wahrscheinlichMöglichkeiten, dies zuumgehen, aber ich würde das lieber nicht tun. $\left[\varphi^n / \sqrt{5}\right]$ $n$

Gibt es einen effizienten (logarithmischen im Wert oder besser) Algorithmus, um die te Fibonacci-Zahl zu berechnen , die nicht auf Gleitkomma-Arithmetik beruht? Nehmen Sie an, dass Ganzzahloperationen ( , , , ) in konstanter Zeit ausgeführt werden können. $n$ $n$ $+$ $-$ $\times$ $/$

algorithms time-complexity recurrence-relation augurar
quelle

5

Der Wikipedia-Artikel über Fibonacci-Zahlen enthält viele Methoden.

Pseudonym

vgl. stackoverflow.com/questions/14661633/… und Links darin und in der Umgebung.

Will Ness

14

Sie können Matrix-Powering und die Identität In Ihrem Berechnungsmodell ist dies ein -Algorithmus, wenn Sie das Powering durch wiederholtes Quadrieren implementieren.

{[\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
quelle

1

Es ist ein Klassiker.

dfeuer

8

Sie können diese Identität auch verwenden, um die Wiederholungen

und

abzuleiten .

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

Sie können diesen mathematischen Artikel lesen: Ein schneller Algorithmus zur Berechnung großer Fibonacci-Zahlen (Daisuke Takahashi): PDF .

Einfacher ausgedrückt, habe ich mehrere Fibonacci-Algorithmen in C ++ (ohne und mit GMP) und Python implementiert. Komplette Quellen auf Bitbucket. Auf der Hauptseite können Sie auch Links folgen zu:

Die C ++ HTML Online-Dokumentation.
Ein kleines mathematisches Dokument: Fibonacci-Zahlen - verschiedene Relationen, um gute Algorithmen zu implementieren

Die nützlichsten Formeln sind:

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

Seien Sie vorsichtig beim Algorithmus. Sie dürfen nicht mehrmals denselben Wert berechnen. Ein einfacher rekursiver Algorithmus (in 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)

Seine Komplexität ist logarithmisch (wenn die Grundoperationen in konstanter Zeit ablaufen): . $O(\log n)$

Olivier Pirson
quelle

2

Willkommen in der Informatik . Können Sie Ihrer Antwort weitere Informationen hinzufügen? Momentan sind es nicht mehr als zwei Links, sodass Ihre Antwort bedeutungslos wird, wenn diese Links sterben oder die Server, auf denen sie sich befinden, nicht verfügbar sind. Links zu weiteren Informationen sind in Ordnung, aber die Links hier sind die einzigen Informationen. Beachten Sie auch, dass es sich bei der Frage eindeutig um Algorithmen handelt, nicht um C ++ - Implementierungen. Implementierungen tendieren dazu, die Algorithmen hinter sprachspezifischen Details zu verschleiern.

David Richerby

David, der erste Link ist ein Link zu einem mathematischen Artikel. Der Titel Ein schneller Algorithmus [...] beantwortet die Frage "Gibt es einen effizienten (logarithmischen im Wert n oder besser) Algorithmus [...]?" Der zweite Link ist ein Link zu meinen verschiedenen Implementierungen in C ++ und Python sowie ein kleines mathematisches Dokument mit mehreren Formeln.

Olivier Pirson

2

Nein, der Titel des Artikels, den Ihre Antwort enthält, beantwortet nichts. Der Text des Artikels, von dem Ihre Antwort so gut wie keinen enthält, scheint die Frage wahrscheinlich zu beantworten. Stack Exchange ist jedoch eine Frage- und Antwortsite, keine Linkfarm. (Und nein, ich schlage nicht vor, dass Sie den Artikel kopieren und in Ihre Antwort einfügen. Es wird jedoch eine Zusammenfassung benötigt.)

David Richerby

Wenn Sie eine Zusammenfassung wünschen, schreiben Sie sie!

Olivier Pirson

0

Grundlegende Theorie und Code zur Berechnung linearer Wiederholungen mit konstanten Koeffizienten in $O(\log_2 n)$ ist abrufbar unter http://www.jjj.de/ .

Überprüfen Sie das kostenlose Buch Matters Computational und den Pari- / GP-Code.

joro
quelle

5

Es ist besser, die Ideen zusammenzufassen, als nur Links zu posten.

26.

Effizienter Algorithmus zur Berechnung der

Antworten: