Numpy Matrix Exponentiation ergibt negativen Wert

Question

Ich wollte NumPy in einer Fibonacci Frage wegen seiner Effizienz in der Matrix-Multiplikation verwenden. Sie wissen, dass es eine Methode zum Finden von Fibonacci-Zahlen mit der Matrix [[1, 1], [1, 0]] gibt.

Ich schrieb einige sehr einfachen Code aber nach n zunimmt, wird die Matrix negative Zahlen zu geben beginnen.

import numpy 
def fib(n): 
    return (numpy.matrix("1 1; 1 0")**n).item(1) 

print fib(90) 
# Gives -1581614984 

Was könnte der Grund dafür sein?

Hinweis:linalg.matrix_power gibt auch negative Werte.

Hinweis2: Ich habe versucht Zahlen von 0 bis 100. Es beginnt nach 47 geben negative Werte. Ist es ein großes ganzzahliges Problem, weil NumPy in C codiert ist? Wenn ja, wie könnte ich das lösen?

Edit: Verwendung von regulären Python list Matrix mit linalg.matrix_power gab auch negative Ergebnisse. Auch lassen Sie mich hinzufügen, dass nicht alle Ergebnisse nach 47 negativ sind, geschieht es zufällig.

Edit2: Ich versuchte mit der Methode @ AlbertoGarcia-Raboso vorgeschlagen. Es löste das Problem mit der negativen Zahl, jedoch traten weitere Probleme auf. Es gibt die Antwort als -5.168070885485832e+19 wo ich -51680708854858323072L brauche. Also habe ich versucht mit int(), es konvertiert es in L, aber jetzt scheint es die Antwort ist falsch wegen eines Verlustes an Genauigkeit.

Answer 1

Der Grund dafür, dass negative Werte angezeigt werden, liegt darin, dass NumPy standardmäßig np.int32 dtype für Ihre Matrix verwendet hat.

Die maximale positive ganze Zahl darstellen kann diese dtype 2 -1 ist, die 2147483647 Leider ist dies weniger der 47th Fibonacci-Zahl, 2971215073. Die sich ergebende Überlauf die negative Zahl verursacht erscheinen:

>>> np.int32(2971215073) 
-1323752223 

Die Verwendung eines größeren Integer-Typs (wie np.int64) würde dies beheben, aber nur vorübergehend: Sie würden immer noch Probleme bekommen, wenn Sie weiter nach größeren und größeren Fibonacci-Zahlen fragen würden.

Die einzige sichere Lösung ist die Verwendung eines Integer-Typs unbegrenzter Größe, wie Pythons int Typ. Um dies zu tun, ändern Sie Ihre Matrix von np.object Typ sein:

def fib_2(n): 
    return (np.matrix("1 1; 1 0", dtype=np.object)**n).item(1) 

Der np.object Typ ermöglicht eine Matrix oder ein Array einer beliebige Mischung aus nativen Python-Typen zu halten. Im Wesentlichen verhält sich die Matrix, anstatt Maschinentypen zu halten, jetzt wie eine Python-Liste und besteht einfach aus Zeigern auf ganzzahlige Objekte im Speicher. Python-Integer werden jetzt bei der Berechnung der Fibonacci-Zahlen verwendet und ein Überlauf ist kein Problem.

>>> fib_2(300) 
222232244629420445529739893461909967206666939096499764990979600 

Diese Flexibilität geht auf Kosten einer verringerten Leistung: NumPy der Geschwindigkeit stammt aus direkter Speicherung von integer/float-Typen, die von Ihrer Hardware manipuliert werden kann.