Schnelle Fibonacci -Berechnung ⇐ Python

[Anonymous]

Ich habe vor einigen Wochen einen Kommentar zu Google+ gesehen, in dem jemand eine einfache Berechnung von Fibonacci-Zahlen demonstrierte, die nicht auf einer Rekursion basierte und keine Memoisierung verwendete. Er erinnerte sich effektiv an die letzten 2 Zahlen und fügte sie weiter hinzu. Dies ist ein O (N) -Algorithmus, aber er hat ihn sehr sauber implementiert. Daher habe ich schnell darauf hingewiesen, dass ein schnellerer Weg darin besteht, die Tatsache zu nutzen, dass sie als Potenzen von [[0,1], [1,1]] -Matrix berechnet werden können und nur ein o (log (n)) erforderlich ist Berechnung. < /p>

Das Problem ist natürlich, dass dies weit davon entfernt ist, einen bestimmten Punkt optimal zu überschreiten. Es ist effizient, solange die Zahlen nicht zu groß sind, aber sie wachsen mit der Geschwindigkeit von N*log (PHI)/log (10), wobei n die n -te Fibonacci -Zahl und PHI das goldene Verhältnis ist ((1 +sqrt (5))/2 ~ 1,6). Wie sich herausstellt, liegt Log (PHI)/Log (10) sehr nahe bei 1/5. Es ist also zu erwarten, dass die N -te Fibonacci -Zahl ungefähr N/5 -Ziffern hat. < /p>

Matrix -Multiplikation, sogar Zahlenmultiplikation, wird sehr langsam, wenn die Zahlen Millionen oder Milliarden Ziffern haben. Die F (100.000) dauerte also ungefähr 0,03 Sekunden, um zu berechnen (in Python), während F (1000.000) ungefähr 5 Sekunden dauerte. Dies ist kaum O (log (n)) Wachstum. Meine Schätzung war, dass diese Methode ohne Verbesserungen nur die Berechnung auf o ((log (n)) ^ (2.5)) oder so optimiert. < /p>

Berechnung einer Milliardstelfibonacci-Zahl wäre bei dieser Geschwindigkeit unerschwinglich langsam (obwohl es nur ~ 1.000.000.000 /5 Ziffern hätte, so dass es leicht in 32-Bit-Speicher passt ). Vielleicht etwas, das die Berechnung einer billionsten Fibonacci -Zahl ermöglichen würde. < /p>

Und um nur klar zu sein, suche ich keine Annäherung. Ich suche die genaue Berechnung (bis zur letzten Ziffer). Python -Code, um zu zeigen, was ich glaube, ist o ((log n) ^ 2.5)) Algorithmus. < /P>

Code: Select all

from operator import mul as mul
from time import clock

class TwoByTwoMatrix:
__slots__ = "rows"

def __init__(self, m):
self.rows = m

def __imul__(self, other):
self.rows = [[sum(map(mul, my_row, oth_col)) for oth_col in zip(*other.rows)] for my_row in self.rows]
return self

def intpow(self, i):
i = int(i)
result = TwoByTwoMatrix([[long(1),long(0)],[long(0),long(1)]])
if i >= 1
multiplier = TwoByTwoMatrix(self.rows)
while i > 0:
if i & 1:
result *= multiplier
multiplier *= multiplier # square it
i >>= 1
for j in xrange(k):
result *= result
return result

m = TwoByTwoMatrix([[0,1],[1,1]])

t1 = clock()
print len(str(m.intpow(100000).rows[1][1]))
t2 = clock()
print t2 - t1

t1 = clock()
print len(str(m.intpow(1000000).rows[1][1]))
t2 = clock()
print t2 - t1
< /code>

[b] Bearbeiten 2: < /strong>
Es sieht so aus, als hätte ich nicht die Tatsache ausgerechnet, dass Len (Str (...)) 

würde einen erheblichen Beitrag zur Gesamtlaufzeit des Tests leisten. Tests in < /p>

ändern

Code: Select all

from math import log as log

t1 = clock()
print log(m.intpow(100000).rows[1][1])/log(10)
t2 = clock()
print t2 - t1

t1 = clock()
print log(m.intpow(1000000).rows[1][1])/log(10)
t2 = clock()
print t2 - t1
< /code>

verkürzte die Laufzeiten auf 0,008 Sekunden und 0,31 Sekunden (ab 0,03 Sekunden und 5 Sekunden, als Len (Str (...)) < /code> verwendet wurde ). -1)], [f (n-1), f (n)]],
Die andere offensichtliche Quelle der Ineffizienz war die Berechnung (0,1) und (1,0) Elemente der Matrix, als ob sie sie waren unterschiedlich.   Dies (und ich wechselte zu Python3, aber Python2.7 -mal ähnlich): < /p>

class SymTwoByTwoMatrix():
# elments (0,0), (0,1), (1,1) of a symmetric 2x2 matrix are a, b, c.
# b is also the (1,0) element because the matrix is symmetric

def __init__(self, a, b, c):
self.a = a
self.b = b
self.c = c

def __imul__(self, other):
# this multiplication does work correctly because we
# are multiplying powers of the same symmetric matrix
self.a, self.b, self.c = \
self.a * other.a + self.b * other.b, \
self.a * other.b + self.b * other.c, \
self.b * other.b + self.c * other.c
return self

def intpow(self, i):
i = int(i)
result = SymTwoByTwoMatrix(1, 0, 1)
if i >= 1
multiplier = SymTwoByTwoMatrix(self.a, self.b, self.c)
while i > 0:
if i & 1:
result *= multiplier
multiplier *= multiplier # square it
i >>= 1
for j in range(k):
result *= result
return result
< /code>

Berechnet F (100.000) in 0,006, F (1.000.000) in .235 und F (10.000.000) in 9,51 Sekunden.  < /p>

, was zu erwarten ist.  Es erzeugt die Ergebnisse 45% schneller für den schnellsten Test und es wird erwartet, dass der Gewinn asymptotisch
phi /(1+2*PHI+PHI*PHI) ~ 23,6%. < /P>
nähern sollte
Das (0,0) Element von m^n ist eigentlich n-2nd Fibonacci-Nummer: < /p>

for i in range(15):
x = m.intpow(i)
print([x.a,x.b,x.c])
< /code>

Gibt < /p>

an[1, 0, 1]
[0, 1, 1]
[1, 1, 2]
[1, 2, 3]
[2, 3, 5]
[3, 5, 8]
[5, 8, 13]
[8, 13, 21]
[13, 21, 34]
[21, 34, 55]
[34, 55, 89]
[55, 89, 144]
[89, 144, 233]
[144, 233, 377]
[233, 377, 610]
< /code>

Ich würde erwarten, dass das Element (0,0) nicht berechnen muss .  Aber die LRU_Cache 

von F (2n) und F (2n-1), die von Eli Korvigo unten angegeben ist, ergibt tatsächlich eine Geschwindigkeit von 4-mal [/b] (dh 75%). Obwohl ich keine formale Erklärung ausgearbeitet habe, bin ich versucht zu glauben, dass es die Spannweiten von 1 innerhalb der binären Expansion von N zwischengeschnitten und die minimale Anzahl der notwendigen Multiplikationen durchführt. Das vermeidet die Notwendigkeit, diese Bereiche zu finden, sie vorzubeugen und sie dann mit dem richtigen Punkt in der Erweiterung von N. LRU_Cache zu multiplizieren -Top Berechnung. Jedes Mal zu berechnen, wenn N 10 Mal wächst. Ich denke, das liegt möglicherweise an der Implementierung der Multiplikation langer INTs durch Python. Ich denke, die Multiplikation großer Zahlen und ihre Ergänzung sollten parallelisierbar sein. Eine Multi-Thread-Sub-O (n) -Lösung sollte also möglich sein, obwohl (wie Daniel Fisher in Kommentaren feststellt) die F (n) -Lösung ist Theta (n) .