n-te Fibonacci-Zahl in sublinearer Zeit

76

Gibt es einen Algorithmus zur Berechnung der n-ten Fibonacci-Zahl in sublinearer Zeit?

Biswajyoti Das
quelle
4
Man könnte argumentieren, dass es sich um Algorithmen handelt, da das OP einen vagen Hinweis auf die algorithmische Komplexität gibt ... Ich wäre trotzdem gespannt, welcher Algorithmus.
Matthew Scharley
2
Die beiden folgenden Antworten haben die richtige Formel. Ob diese Frage mit der Programmierung zusammenhängt: Sie ist Teil der Informatik. Die zur Ableitung der Formel verwendete Vorrichtung ist als "Erzeugungsfunktionen" bekannt und spielt eine wichtige Rolle bei der Algorithmusanalyse.
Azheglov
1
@azheglov: Während das Generieren von Funktionen nützlich ist, werden sie nicht benötigt, um den Ausdruck in geschlossener Form für die Fibonacci-Sequenz abzuleiten.
Jason
7
Sie haben ein Problem, das Sie aus irgendeinem Grund lösen möchten, und Sie möchten es effizient erledigen. Manchmal ist die erforderliche Einsicht eine neue Implementierung, manchmal ein Algorithmus und manchmal Mathematik. Es ist nicht erforderlich, die Situation jedes Mal als "nicht programmierbezogen" zu entschlüsseln.
ShreevatsaR
7
Die Größe des Ergebnisses ist in n linear. Daher gibt es keinen solchen Algorithmus. Das macht natürlich keine der netten Antworten ungültig, die Fibonacci-Zahlen mit O (log n) -Arithmetikoperationen berechnen.
Accipitridae

Antworten:

66

Die nth Fibonacci-Zahl ist gegeben durch

f(n) = Floor(phi^n / sqrt(5) + 1/2) 

wo

phi = (1 + sqrt(5)) / 2

Unter der Annahme , dass die primitiven mathematischen Operationen ( +, -, *und /) sind O(1)Sie dieses Ergebnis können Sie die berechnen nth Fibonacci - Zahl in der O(log n)Zeit ( O(log n)wegen der Potenzierung in der Formel).

In C #:

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
Jason
quelle
7
@Json Ich habe Sie nicht herabgestimmt, aber andere tun dies möglicherweise, weil Ihre Antwort darauf hindeutet, dass die N-te Fibonacci-Zahl in O (log n) -Zeit berechnet werden kann, was falsch ist. Ihr Code berechnet eine Annäherung. Ihr Code wäre mindestens O (n) in beliebiger Genauigkeit, da die Länge der Antwort O (n) ist.
PeterAllenWebb
10
@PeterAllenWebb: Die angegebene Formel ist keine Annäherung. Die n-te Fibonacci-Zahl entspricht dem Boden von phi^n / sqrt(5) + 1/2wo phi = (1 + sqrt(5)) / 2. Das ist ein Fakt. Zweitens verstehe ich den Punkt, den andere über die Länge der Antwort machen, O(n)aber ich habe meiner Antwort eine Bemerkung hinzugefügt, unter der Annahme, dass die primitiven mathematischen Operationen eine konstante Zeit benötigen (ich weiß, dass dies nicht der Fall ist, wenn Sie die Eingaben nicht gebunden haben). Mein Punkt ist, dass wir die n-te Fibonacci-Zahl in O(log n)arithmetischen Operationen finden können.
Jason
4
@ Jason: Unter der Annahme, dass die Potenzierung auch O (1) ist, wird der gesamte Algorithmus zu O (1). Das wäre schön, aber die Potenzierung ist nicht O (1) und auch nicht die anderen primitiven mathematischen Operationen. Kurz gesagt, die Formel ist nett, berechnet aber das Ergebnis nicht in sublinearer Zeit.
Yairchu
12
@Jason: Die Formel ist keine Annäherung, aber der Code ist eine Annäherung (außer bei einer imaginären C # -Implementierung, bei der Math.Pow (…) unendlich genau ist. In diesem Fall ist der Code O (n)).
ShreevatsaR
14
@ Jason: Nein. Führen Sie Ihren Code auf n = 1000 aus (für die die Fibonacci-Nummer 43466 ... 849228875 nur 209 Ziffern hat) und sagen Sie mir, ob Sie alle Ziffern richtig verstanden haben. Damit Math.Floor den ganzzahligen Teil richtig macht, müssen diese vielen Ziffern von Math.Pow genau berechnet werden. In meiner C ++ - Implementierung wird sogar die 16-stellige F_ {74} = 130496954492865 falsch berechnet, obwohl die Ganzzahl 130496954492865 genau (mit langer Länge) dargestellt werden kann, und ich wäre überrascht, wenn C # viel mehr Ziffern erhält als die.
ShreevatsaR
100

Aus Pillsys Verweis auf die Matrixexponentiation folgt, so dass für die Matrix

M = [1 1]
    [1 0] 

dann

fib ( n ) = M n 1,2

Das Erhöhen von Matrizen auf Potenzen durch wiederholte Multiplikation ist nicht sehr effizient.

Zwei Ansätze zur Matrixexponentiation sind Teilen und Erobern, was M n in O ( ln n ) Schritten ergibt , oder Eigenwertzerlegung, die zeitlich konstant ist, aber aufgrund der begrenzten Gleitkommapräzision Fehler verursachen kann.

Wenn Sie einen exakten Wert wünschen, der größer ist als die Genauigkeit Ihrer Gleitkommaimplementierung, müssen Sie den O (ln n) -Ansatz verwenden, der auf dieser Beziehung basiert:

M n = ( M n / 2 ) 2, wenn n gerade ist
   = M · M n -1, wenn n ungerade ist

Die Eigenwertzerlegung auf M findet zwei Matrizen U und Λ, so dass Λ diagonal und ist

 M   = U  Λ  U -1  
 M n = ( U  Λ  U -1 ) n 
    = U  Λ  U -1  U  Λ  U -1  U  Λ  U -1 ... n-mal
    = U  Λ  Λ  Λ ... U -1  
    = U  Λ  n  U -1 
Das Erhöhen der Diagonalmatrix Λ auf die n- te Potenz ist eine einfache Sache, bei der jedes Element in Λ auf die n - te Potenz angehoben wird. Dies ergibt eine O (1) -Methode zum Erhöhen von M auf die n- te Potenz. Es ist jedoch unwahrscheinlich, dass die Werte in Λ Ganzzahlen sind, sodass ein Fehler auftritt.

Definieren Sie Λ für unsere 2x2-Matrix als

Λ = [λ 1 0]
  = [0 λ 2 ]

Um jedes λ zu finden , lösen wir

| M - λ I | = 0

was gibt

| M - λ I | = -λ (1 - λ) - 1

λ² - λ - 1 = 0

mit der quadratischen Formel

λ = (-b ± √ (b² - 4ac)) / 2a
     = (1 ± √5) / 2
 {λ 1 , λ 2 } = {Φ, 1-Φ} wobei Φ = (1 + √5) / 2

Wenn Sie Jasons Antwort gelesen haben, können Sie sehen, wohin das führen wird.

Auflösen nach den Eigenvektoren X 1 und X 2 :

wenn X 1 = [ X 1,1 , X 1,2 ]

 M . X 1 1 = λ 1 X 1

 X 1,1 + X 1,2 = λ 1  X 1,1 
 X 1,1       = λ 1  X 1,2

=>
 X 1 = [Φ, 1]
  X 2 = [1-Φ, 1]

Diese Vektoren ergeben U :

U = [ X 1,1 , X 2,2 ]
    [ X 1,1 , X 2,2 ]

  = [Φ, 1-Φ]
    [1, 1]

U invertieren mit

A    = [ab]
      [cd]
=>
A -1 = (1 / | A |) [d -b]
                   [-ca]

also ist U -1 gegeben durch

U -1 = (1 / (Φ - (1 - Φ)) [1 Φ-1]
                               [-1 Φ]
U -1 = (√5) -1   [1 Φ-1]
               [-1 Φ]

Gesundheitsüberprüfung:

UΛU -1 = (√5) -1 [Φ 1-Φ]. [Φ 0]. [1 Φ-1]
                     [1 1] [0 1-Φ] [-1 Φ]

sei Ψ = 1-Φ, der andere Eigenwert

als Φ ist eine Wurzel von λ²-λ-1 = 0 
also -ΨΦ = Φ²-Φ = 1
und Ψ + Φ = 1

UΛU -1 = (√5) -1 [Φ Φ]. [Φ 0]. [1 -Ψ]
                 [1 1] [0 Ψ] [-1 Φ]

       = (√5) -1 [Φ Φ]. [Φ -ΨΦ]
                 [1 1] [-Ψ ΨΦ]

       = (√5) -1 [Φ Φ]. [Φ 1]
                 [1 1] [-Ψ -1]

       = (√5) -1 [Φ²-Ψ² Φ-Ψ]
                  [Φ-Ψ 0]

       = [Φ + Ψ 1]    
         [1 0]

       = [1 1] 
         [1 0]

       = M. 

Der Sanity Check gilt also.

Jetzt haben wir alles, was wir brauchen, um M n 1,2 zu berechnen :

M n = U Λ n U -1 
   = (√5) -1 [Φ Φ]. [Φ n   0]. [1 -Ψ]
              [1 1] [0 Ψ n ] [-1 Φ]

   = (√5) -1 [Φ Φ]. [Φ n   -ΨΦ n ]
              [1 1] [-Ψ n    Ψ n Φ]

   = (√5) -1 [Φ Φ]. [Φ n    Φ n -1 ]
              [1 1] [-Ψ nn -1 ] als ΨΦ = -1

   = (√5) -1n + 1 - Ψ n + 1       Φ n - Ψ n ]
              [Φ nn       Φ n -1n -1 ]

damit

 fib ( n ) = M n 1,2 
        = (Φ n - (1 - Φ) n ) / √5

Was mit der an anderer Stelle angegebenen Formel übereinstimmt.

Sie können es aus einer Wiederholungsrelation ableiten, aber beim Engineering-Computing und der Simulation ist die Berechnung der Eigenwerte und Eigenvektoren großer Matrizen eine wichtige Aktivität, da sie Stabilität und Harmonische von Gleichungssystemen bietet und es ermöglicht, Matrizen effizient auf hohe Leistungen anzuheben.

Pete Kirkham
quelle
+1 - Tolles Zeug, wie immer. Womit haben Sie es gesetzt? Latex?
Duffymo
Es wurde aus dem Buch der Algebra von Gilbert Strang oder aus einem anderen guten Buch der linearen Algebra kopiert.
Alinsoar
1
@alinsoar es wurde nicht 'kopiert' eingefügt, sondern als Übung durchgeführt, um zu überprüfen, ob ich mich noch an meine Lin a erinnern konnte, mit einem Verweis auf Open University Kursnotizen und Wikipedia.
Pete Kirkham
Ich habe mit Gilbert Strang den Kurs der L-Algebra belegt, und dort war er identisch. Das Problem, Rekursion durch Matrixzerlegung auszudrücken, ist klassisch und kann in jedem guten Lehrbuch / Kurs gefunden werden.
Alinsoar
56

Wenn Sie die genaue Zahl wollen (die eher ein "Bignum" als ein Int / Float ist), dann fürchte ich das

Es ist unmöglich!

Wie oben angegeben, lautet die Formel für Fibonacci-Zahlen:

fib n = floor (phi n / √5 + 1 / 2 )

fib n ~ = phi n / √5

Wie viele Ziffern gibt es fib n?

numDigits (fib n) = log (fib n) = log (phi n / √5) = log phi n - log √5 = n * log phi - log √5

numDigits (fib n) = n * const + const

es ist O ( n )

Da das angeforderte Ergebnis O ( n ) ist, kann es nicht in weniger als O ( n ) berechnet werden.

Wenn Sie nur die unteren Ziffern der Antwort wünschen, können Sie mit der Matrix-Exponentiationsmethode in sublinearer Zeit berechnen.

Yairchu
quelle
2
@yairchu: Lass mich das umformulieren, wenn ich es richtig verstehe. Theoretisch erfordert die Berechnung von fib_n die Berechnung von n Ziffern, so dass für jedes beliebige n O (n) Zeit benötigt wird. Wenn jedoch fib_n <sizeof (long long) ist, können wir fib_n in O (log n) berechnen, da die Maschinenarchitektur einen parallelen Mechanismus zum Setzen der Bits bereitstellt. (Zum Beispiel, int i = -1; erfordert das Setzen von 32-Bit, aber auf einem 32-Bit-Computer können alle 32-Bit in konstanter Zeit gesetzt werden.
Summe
7
@Sumit: Wenn Sie nur Ergebnisse unterstützen möchten, die in 32-Bit passen, können Sie auch eine Nachschlagetabelle für diese ersten 48 Ergebnisse der Serie erstellen. Das ist natürlich O (1), aber: Eine Big-O-Analyse für ein begrenztes N durchzuführen ist dumm, da Sie immer alles in den konstanten Faktor einbeziehen können. Meine Antwort bezieht sich also auf unbegrenzte Eingaben.
Yairchu
1
@yairchu: Könnten Sie Ihre Logik für ein bekanntes Beispiel demonstrieren, beispielsweise O(n*log n)für die vergleichsbasierte Sortierung einer Folge von nZahlen, bei denen jede Zahl O(log n)Ziffern hat?
JFS
1
Dies ist richtig oder falsch, je nachdem, was Sie unter "Zeit" verstehen. Für das Sortieren (oder Nachschlagen von Hash-Tabellen) bedeutet "Zeit" die Anzahl der Vergleiche. In der Frage könnte es sich um arithmetische Operationen handeln. In dieser Antwort wird so etwas wie eine ziffernweise Operation verstanden.
Paul Hankin
4
Ganzzahlen haben zwar eine endliche Darstellung in Basis-Quadrat (2), aber sie sind bei ungeraden Ziffern nur Null, dh entspricht Basis 2. Wenn eine der ungeraden Ziffern in Basis-Quadrat (2) ungleich Null ist, haben Sie eine irrationale Zahl . Ein Fall, in dem Sie möglicherweise Basis-Phi wünschen, sind ADCs, wenn Sie kontinuierliche Signale in analoge konvertieren. Afaik dies ist die "industrielle" Anwendung von Basis-Phi, bei der es verwendet wird, um die Grobkörnung beim Runden des Signals zu reduzieren. Persönlich habe ich jedoch Basis-Phi- und Fibonacci-Codierungen als notational bequeme Methode verwendet, um mit Fibonacci-Anyon-Darstellungen der Geflechtgruppe zu arbeiten.
Saolof
34

Eine der Übungen in SICP befasst sich mit dieser Frage , die hier beschrieben wird .

Im imperativen Stil würde das Programm ungefähr so ​​aussehen

Funktion  Fib ( Anzahl )
     a ← 1
     b ← 0
     p ← 0
     q ← 1

    Während  Zählung > 0 Do 
        Wenn Even ( Zählung ) Dann 
             pp ² + q ²
              q ← 2 pq + q ²
              ZahlZählung ÷ 2
         Else 
             abq + aq + ap 
             bbp + aq 
             ZahlZahl - 1
         End If 
    End While

    Return  b 
End Function
Nietzche-jou
quelle
1
Zählung wurde nicht initialisiert
Yairchu
Hier ist eine Implementierung in Python (zur Verwendung mit twistedFramework).
JFS
"If Even (count) Then" sollte "If Odd (count) Then" sein
Monirul Islam Milon
@ MonirulIslamMilon if even(count)ist korrekt. Die Sequenz beginnt mit Null (nullte Fibonacci-Zahl ist Null): 0,1,1,2,3,5,8,13, ...
jfs
Der Buchlink
Lee D
24

Sie können dies tun, indem Sie auch eine Matrix von Ganzzahlen potenzieren. Wenn Sie die Matrix haben

    / 1  1 \
M = |      |
    \ 1  0 /

dann (M^n)[1, 2]wird gleich der nth Fibonacci-Zahl sein, wenn []es sich um einen Matrixindex und eine Matrixexponentiation ^handelt. Für eine Matrix mit fester Größe kann die Exponentiation zu einer positiven Integralleistung in O (log n) -Zeit auf die gleiche Weise wie bei reellen Zahlen erfolgen.

BEARBEITEN: Abhängig von der Art der gewünschten Antwort können Sie möglicherweise mit einem Algorithmus mit konstanter Zeit davonkommen. Wie die anderen Formeln zeigen, nwächst die th Fibonacci-Zahl exponentiell mit n. Selbst bei 64-Bit-Ganzzahlen ohne Vorzeichen benötigen Sie nur eine Nachschlagetabelle mit 94 Einträgen, um den gesamten Bereich abzudecken.

ZWEITE BEARBEITUNG: Das erste Exponential der Matrix mit einer Eigendekomposition entspricht genau der folgenden Lösung von JDunkerly. Die Eigenwerte dieser Matrix sind (1 + sqrt(5))/2und (1 - sqrt(5))/2.

Pillsy
quelle
3
Verwenden Sie die Eigenzerlegung von M, um M ^ n effizient zu berechnen.
Pete Kirkham
1
Die vorgeschlagene Methode eignet sich gut für Berechnungen in ganzen Zahlen (wahrscheinlich mit langer Arithmetik). Ein Ansatz mit Eigenzerlegung ist nicht interessant: Wenn Sie keine ganzzahligen Berechnungen benötigen, verwenden Sie die Formel aus Jasons Antwort.
Konstantin Tenzin
1
@Konstantin Die Formel aus Jasons Antwort ist das Ergebnis der Eigenzerlegung, also widersprechen Sie sich selbst.
Pete Kirkham
@Pete Kirkham Diese Formel kann mit verschiedenen Methoden erhalten werden: Charakteristikgleichung, Eigenzerlegung, Beweis durch Induktion. Ich bin mir nicht sicher, ob die Eigenzerlegung die einfachste ist. In jedem Fall ist es bekannt und es ist einfacher, es sofort zu verwenden
Konstantin Tenzin
5

Wikipedia hat eine geschlossene Lösung http://en.wikipedia.org/wiki/Fibonacci_number

Oder in c #:

    public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) / 2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
        return (int)fn;
    }
JDunkerley
quelle
2
Sie können die Notwendigkeit vermeiden, auf zwei Exponentiale zu berechnen, indem Sie die Tatsache verwenden, dass |1 - phi|^n / sqrt(5) < 1/2when neine nichtnegative Ganzzahl ist.
Jason
Ich
1
Annäherung des Ergebnisses Die richtige Lösung beinhaltet die Matrixmultiplikation.
Cerkiewny
4

Für wirklich große funktioniert diese rekursive Funktion. Es werden die folgenden Gleichungen verwendet:

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

Sie benötigen eine Bibliothek, mit der Sie mit großen Ganzzahlen arbeiten können. Ich benutze die BigInteger-Bibliothek von https://mattmccutchen.net/bigint/ .

Beginnen Sie mit einer Reihe von Fibonacci-Zahlen. Verwenden Sie Fibs [0] = 0, Fibs [1] = 1, Fibs [2] = 1, Fibs [3] = 2, Fibs [4] = 3 usw. In diesem Beispiel verwende ich ein Array der ersten 501 (0 zählen). Die ersten 500 Fibonacci-Zahlen ungleich Null finden Sie hier: http://home.hiwaay.net/~jalison/Fib500.html . Es erfordert ein wenig Bearbeitung, um es in das richtige Format zu bringen, aber das ist nicht zu schwierig.

Dann können Sie mit dieser Funktion (in C) eine beliebige Fibonacci-Zahl finden:

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) // Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) // numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else // numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

Ich habe dies für die 25.000ste Fibonacci-Zahl und dergleichen getestet.

user3137939
quelle
Dieser Code ist nicht so effizient. Stellen Sie sich vor, das fibs [] -Array hat nur Größe 10 und Sie rufen Fib (101) auf. Fib (101) nennt Fib (51) und Fib (50). Fib (51) nennt Fib (26) und Fib (25). Fib (50) ruft Fib (25) und Fib (24) auf. Also wurde Fib (25) zweimal aufgerufen, was eine Verschwendung ist. Selbst mit Fibs bis zu 500 haben Sie das gleiche Problem mit Fib (100000).
Eyal
3

Hier ist meine rekursive Version, die log (n) mal rekursiv ist. Ich denke, dass es am einfachsten ist, in rekursiver Form zu lesen:

def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

Es funktioniert , weil Sie berechnen kann fib(n),fib(n-1)unter Verwendung , fib(n-1),fib(n-2)wenn n ungerade ist , und wenn n gerade ist, können Sie berechnen , fib(n),fib(n-1)verwenden fib(n/2),fib(n/2-1).

Der Basisfall und der ungerade Fall sind einfach. Um den geraden Fall abzuleiten, beginnen Sie mit a, b, c als aufeinanderfolgende Fibonacci-Werte (z. B. 8,5,3) und schreiben Sie sie in eine Matrix mit a = b + c. Beachten:

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

Daraus sehen wir, dass eine Matrix der ersten drei Fibonacci-Zahlen, mal eine Matrix aus drei aufeinanderfolgenden Fibonacci-Zahlen, gleich der nächsten ist. Also wissen wir das:

      n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

Damit:

      2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

Die Vereinfachung der rechten Seite führt zum geraden Fall.

Eyal
quelle
Ich möchte hier betonen, dass Sie F (2n) und F (2n + 1) in Funktion von F (n) und F (n-1) berechnen möchten. Sie haben nicht angegeben, was Sie tun möchten.
Alinsoar
1

mit R.

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765
George Dontas
quelle
1

Die Festkomma-Arithmetik ist ungenau. Jasons C # -Code gibt eine falsche Antwort für n = 71 (308061521170130 anstelle von 308061521170129) und darüber hinaus.

Verwenden Sie für eine korrekte Antwort ein Computeralgebrasystem. Sympy ist eine solche Bibliothek für Python. Es gibt eine interaktive Konsole unter http://live.sympy.org/ . Kopieren Sie diese Funktion und fügen Sie sie ein

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

Dann berechnen

>>> f(10)
55

>>> f(71)
308061521170129

Vielleicht möchten Sie versuchen, zu inspizieren phi.

Oberst Panik
quelle
1

Abgesehen von der Feinabstimmung durch mathematische Ansätze besteht eine der besten optimalen Lösungen (glaube ich) darin, ein Wörterbuch zu verwenden, um wiederholte Berechnungen zu vermeiden.

import time

_dict = {1:1, 2:1}

def F(n, _dict):
    if n in _dict.keys():
        return _dict[n]
    else:
        result = F(n-1, _dict) + F(n-2, _dict)
        _dict.update({n:result})
        return result

start = time.time()

for n in range(1,100000):
    result = F(n, _dict) 

finish = time.time()

print(str(finish - start))

Wir beginnen mit einem einfachen Wörterbuch (die ersten beiden Werte der Fibonacci-Sequenz) und fügen dem Wörterbuch ständig Fibonacci-Werte hinzu.

Die ersten 100000 Fibonacci-Werte (Intel Xeon CPU E5-2680 bei 2,70 GHz, 16 GB RAM, Windows 10-64-Bit-Betriebssystem) dauerten etwa 0,7 Sekunden.

bilalsamioguz
quelle
Dies ist jedoch in linearer Zeit, die Frage fragt speziell, wie eine sublineare Zeit erreicht werden kann (was mit einer Art geschlossener Lösung möglich ist).
Romeo Valentin
0

Siehe hier den Algorithmus zum Teilen und Erobern

Der Link hat einen Pseudocode für die Matrixexponentiation, die in einigen anderen Antworten auf diese Frage erwähnt wurde.

Chinmay Lokesh
quelle
0

Sie können die seltsame Quadratwurzelgleichung verwenden, um eine genaue Antwort zu erhalten. Der Grund ist, dass $ \ sqrt (5) $ am Ende herausfällt. Sie müssen nur die Koeffizienten mit Ihrem eigenen Multiplikationsformat verfolgen.

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55
Ihm
quelle
0

Hier ist ein Einzeiler, der F (n) unter Verwendung von ganzen Zahlen der Größe O (n) in O (log n) -Arithmetikoperationen berechnet:

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Die Verwendung von ganzen Zahlen der Größe O (n) ist sinnvoll, da dies mit der Größe der Antwort vergleichbar ist.

Um dies zu verstehen, sei phi der goldene Schnitt (die größte Lösung für x ^ 2 = x + 1) und F (n) die n-te Fibonacci-Zahl, wobei F (0) = 0, F (1) = F. (2) = 1

Nun ist phi ^ n = F (n-1) + F (n) phi.

Beweis durch Induktion: phi ^ 1 = 0 + 1 * phi = F (0) + F (1) phi. Und wenn phi ^ n = F (n-1) + F (n) phi, dann ist phi ^ (n + 1) = F (n-1) phi + F (n) phi ^ 2 = F (n-1) phi + F (n) (phi + 1) = F (n) + (F (n) + F (n - 1)) phi = F (n) + F (n + 1) phi. Der einzige schwierige Schritt bei dieser Berechnung ist der, der phi ^ 2 durch (1 + phi) ersetzt, was folgt, weil phi der goldene Schnitt ist.

Auch Zahlen der Form (a + b * phi), wobei a, b ganze Zahlen sind, werden unter Multiplikation geschlossen.

Beweis: (p0 + p1 · phi) (q0 + q1 · phi) = p0q0 + (p0q1 + q1p0) phi + p1q1 · phi ^ 2 = p0q0 + (p0q1 + q1p0) phi + p1q1 * (phi + 1) = ( p0q0 + p1q1) + (p0q1 + q1p0 + p1q1) * phi.

Mit dieser Darstellung kann man Phi ^ n in O (log n) Integer-Operationen unter Verwendung von Exponentiation durch Quadrieren berechnen. Das Ergebnis ist F (n-1) + F (n) phi, woraus man die n-te Fibonacci-Zahl ablesen kann.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

Beachten Sie, dass der Großteil dieses Codes eine Standardfunktion zur Potenzierung durch Quadrieren ist.

Um auf die Einzeiler , die diese Antwort beginnt, kann man feststellen , dass repräsentiert phi durch eine ausreichend große ganze Zahl X, kann man durchführen (a+b*phi)(c+d*phi)als Integer - Operation (a+bX)(c+dX) modulo (X^2-X-1). Dann powkann die Funktion durch die Standard-Python- powFunktion ersetzt werden (die bequemerweise ein drittes Argument enthält, zdas das Ergebnis modulo berechnet z. Das Xgewählte ist 2<<i.

Paul Hankin
quelle
0

Ich bin auf einige der Methoden zur Berechnung von Fibonacci mit effizienter Zeitkomplexität gestoßen.

Methode 1 - Dynamische Programmierung Nun ist hier die Unterstruktur allgemein bekannt, daher werde ich direkt zur Lösung springen -

static int fib(int n) 
{ 
int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
int i; 

f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
}

Eine platzoptimierte Version von oben kann wie folgt durchgeführt werden:

static int fib(int n) 
 { 
    int a = 0, b = 1, c; 
    if (n == 0) 
        return a; 
    for (int i = 2; i <= n; i++) 
    { 
        c = a + b; 
        a = b; 
        b = c; 
    } 
    return b; 
} 

Methode 2- (Verwenden der Potenz der Matrix {{1,1}, {1,0}})

Dies ist ein O (n), das auf der Tatsache beruht, dass, wenn wir die Matrix M = {{1,1}, {1,0}} n-mal mit sich selbst multiplizieren (mit anderen Worten die Leistung (M, n) berechnen), dann Wir erhalten die (n + 1) -te Fibonacci-Zahl als Element in Zeile und Spalte (0, 0) in der resultierenden Matrix. Diese Lösung hätte O (n) Zeit.

Die Matrixdarstellung gibt den folgenden geschlossenen Ausdruck für die Fibonacci-Zahlen: Fibonaccimatrix

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

/*multiplies 2 matrices F and M of size 2*2, and 
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

/*function that calculates F[][] raise to the power n and puts the 
result in F[][]*/
static void power(int F[][], int n) 
{ 
int i; 
int M[][] = new int[][]{{1,1},{1,0}}; 

// n - 1 times multiply the matrix to {{1,0},{0,1}} 
for (i = 2; i <= n; i++) 
    multiply(F, M); 
} 

Dies kann optimiert werden, um in O (Logn) -Zeitkomplexität zu arbeiten. Wir können eine rekursive Multiplikation durchführen, um die Leistung (M, n) in der vorherigen Methode zu erhalten.

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

static void multiply(int F[][], int M[][]) 
{ 
int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

static void power(int F[][], int n) 
{ 
if( n == 0 || n == 1) 
  return; 
int M[][] = new int[][]{{1,1},{1,0}}; 

power(F, n/2); 
multiply(F, F); 

if (n%2 != 0) 
   multiply(F, M); 
} 

Methode 3 (O (log n) Zeit) Nachfolgend finden Sie eine weitere interessante Wiederholungsformel, mit der die n-te Fibonacci-Zahl in O (log n) Zeit ermittelt werden kann.

Wenn n gerade ist, dann ist k = n / 2: F (n) = [2 · F (k - 1) + F (k)] · F (k)

Wenn n ungerade ist, dann ist k = (n + 1) / 2 F (n) = F (k) * F (k) + F (k-1) * F (k-1) Wie funktioniert diese Formel? Die Formel kann aus der obigen Matrixgleichung abgeleitet werden. Fibonaccimatrix

Wenn wir die Determinante auf beiden Seiten nehmen, erhalten wir (-1) n = Fn + 1Fn-1 - Fn2. Da außerdem AnAm = An + m für jede quadratische Matrix A ist, können die folgenden Identitäten abgeleitet werden (sie werden aus zwei verschiedenen Koeffizienten von erhalten das Matrixprodukt)

FmFn + Fm-1Fn-1 = Fm + n-1

Indem Sie n = n + 1 setzen,

FmFn + 1 + Fm-1Fn = Fm + n

Setzen von m = n

F2n-1 = Fn2 + Fn-12

F2n = (Fn-1 + Fn + 1) Fn = (2Fn-1 + Fn) Fn (Quelle: Wiki)

Um die Formel zu beweisen, müssen wir einfach Folgendes tun: Wenn n gerade ist, können wir k = n / 2 setzen. Wenn n ungerade ist, können wir k = (n + 1) / 2 setzen

public static int fib(int n) 
{ 

    if (n == 0) 
        return 0; 

    if (n == 1 || n == 2) 
        return (f[n] = 1); 

    // If fib(n) is already computed 
    if (f[n] != 0) 
        return f[n]; 

    int k = (n & 1) == 1? (n + 1) / 2 
                        : n / 2; 

    // Applyting above formula [See value 
    // n&1 is 1 if n is odd, else 0. 
    f[n] = (n & 1) == 1? (fib(k) * fib(k) +  
                    fib(k - 1) * fib(k - 1)) 
                   : (2 * fib(k - 1) + fib(k))  
                   * fib(k); 

    return f[n]; 
} 

Methode 4 - Verwenden einer Formel Bei dieser Methode implementieren wir direkt die Formel für den n-ten Term in der Fibonacci-Reihe. Zeit O (1) Raum O (1) Fn = {[(√5 + 1) / 2] ^ n} / √5

static int fib(int n) { 
double phi = (1 + Math.sqrt(5)) / 2; 
return (int) Math.round(Math.pow(phi, n)  
                    / Math.sqrt(5)); 
} 

Referenz: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

der Alchemist
quelle
0

Wir sollten zunächst beachten Sie, dass Fibonacci - Zahlen (F(n))wachsen sehr schnell mit nund kann nicht in dargestellt werden 64 Bits für ngrößer als 93. So ein Programm für sie für eine solche Berechnung nBedarf zusätzliche Mechanismen zu verwenden , auf diesen großen Zahlen zu operieren. Wenn man nur die Anzahl der Operationen (mit großer Anzahl) berücksichtigt, erfordert der Algorithmus, um sie sequentiell zu berechnen, eine lineare Anzahl von Operationen.

Wir können von der folgenden Identität über Fibonacci-Zahlen profitieren:

F(2m) = 2*F(m)*F(m+1) − (F(m))^2

F(2m+1) = (F(m))^2 + (F(m+1))^2

(Ein Symbol wie A ^ 2 bezeichnet das Quadrat von A).

Also, wenn wir wissen , F(m)und F(m+1)können wir direkt berechnen F(2m)und F(2m+1).

Betrachten Sie die binäre Darstellung von n. Beachten Sie, dass x = 1wir beginnend mit x = niterativ verdoppeln und möglicherweise 1 hinzufügen können x. Dies kann durch Iterieren über die Bits von nund Überprüfen, ob es 0 oder 1 ist, erfolgen.

Die Idee ist, dass wir F(x)synchron bleiben können x. In jeder solchen Iteration können wir, wenn wir verdoppeln xund möglicherweise 1 addieren x, auch den neuen Wert der F(x)Verwendung des früheren Werts von F(x)und F(x+1)mit den obigen Gleichungen berechnen.

Da die Anzahl der Iterationen logarithmisch ist n, sind auch die Gesamtoperationen (mit großer Anzahl) logarithmisch n.

Weitere Einzelheiten finden Sie im Abschnitt "Verbesserter Algorithmus" dieses Artikels .

Nitin Verma
quelle