Ungenaue Große Fibonacci-Zahlen in Python

Question

ich zur Zeit mit diesem einfachen Code bin die Umsetzung versucht, das n-te Element der Fibonacci-Folge Python 2.7 unter Verwendung von zu finden:

import numpy as np 

def fib(n): 
     F = np.empty(n+2) 
     F[1] = 1 
     F[0] = 0 
     for i in range(2,n+1): 
      F[i]=F[i-1]+F[i-2] 
     return int(F[n]) 

Dies funktioniert gut für F < 79, aber danach Ich bekomme falsche Zahlen. Zum Beispiel, nach Wolfram alpha F79 sollte gleich 14472334024676221 sein, aber fib(100) gibt mir 14472334024676220. Ich denke, das könnte durch die Art verursacht werden, wie Python mit Ganzzahlen befasst, aber ich habe keine Ahnung, was genau das Problem ist. Jede Hilfe wird sehr geschätzt!

Answer 1

der Standarddatentyp für eine numpy Array ist depending on architecture a 64 (oder 32) Bit Int.

reine Python würde Sie beliebig lange ganze Zahlen haben; numpy nicht.

so ist es die Art und Weise numpy beschäftigt sich mit ganzen Zahlen; reine Python würde gut tun.

Answer 2

Als zusätzliches Wort auf die vorherige Antwort von hiro Protagonisten, beachten Sie, dass, wenn Numpy mit einer Voraussetzung ist, können Sie Ihre Frage sehr easely lösen können durch den Austausch:

F = np.empty(n+2) 

mit

F = np.empty(n+2, dtype=object) 

aber es wird nichts mehr tun, als die Berechnung zurück auf reines Python zu übertragen.

Answer 3

Python wird hier mit ganzen Zahlen völlig in Ordnung. In der Tat, das ist die Schönheit von Python. numpy, auf der anderen Seite, führt Hässlichkeit und nur zufällig völlig unnötig, und wird Sie wahrscheinlich verlangsamen. Ihre Implementierung erfordert auch viel mehr Platz. Mit Python können Sie schönen, lesbaren Code schreiben. Hier ist Raymond Hettinger kanonische Implementierung von iterativen Fibonacci in Python:

def fib(n): 
    x, y = 0, 1 
    for _ in range(n): 
     x, y = y, x + y 
    return x 

Die O (n) Zeit und konstanter Raum ist. Es ist schön, lesbar und prägnant. Es gibt Ihnen auch die richtige Ganzzahl, solange Sie über Speicher verfügen, um die Nummer auf Ihrem Computer zu speichern. Lernen Sie, numpy zu verwenden, wenn es das entsprechende Werkzeug ist, und wie wichtig, lernen Sie zu nicht verwenden Sie es, wenn es unangemessen ist.

Answer 4

Wenn Sie keine Liste mit allen Fibonacci-Zahlen bis Fn erstellen möchten, brauchen Sie keine Liste, numpy oder etwas anderes zu verwenden, eine einfache Schleife und 2 Variablen sind genug, wie Sie wirklich brauchen kennen die zwei vorherigen Werte

def fib(n): 
    Fk, Fk1 = 0, 1 
    for _ in range(n): 
     Fk, Fk1 = Fk1, Fk+Fk1 
    return Fk 

natürlich bessere Möglichkeiten gibt es, es zu tun, die mathematischen Eigenschaften der Fibonacci Nummern, mit denen wir wissen, dass es ein matrix ist, die uns das richtige Ergebnis geben

import numpy 

def fib_matrix(n): 
    mat = numpy.matrix([[1,1],[1,0]], dtype=object) ** n 
    return mat[0,1] 

, von dem ich annehme, dass sie eine optimierte Matrix exponentiation haben, die es effizienter macht, dass die vorherige Methode.

Mit den Eigenschaften der zugrunde liegenden Lucas sequence ist es möglich, ohne die matriz zu tun, und ebenso effizient wie Binäre Exponentiation und mit der gleichen Anzahl von Variablen wie die anderen, aber das ist ein wenig schwieriger, auf dem ersten Blick zu verstehen anders als das erste Beispiel, weil es neben dem zweiten Beispiel mehr mathematisch erfordert.

Die enge Form, die mit dem Goldenen Schnitt, gibt Ihnen das Ergebnis noch schneller, aber das Risiko der Ungenauigkeit wegen der Verwendung von Fließkomma-Arithmetik.