Float mit unbegrenzter Genauigkeit

[Tompazi]

Ich habe eine Funktion geschrieben die mir die Fibbonacci-Zahlen direkt berechnet, da eine rekursive sehr langsam ist.

Code: Alles auswählen

def fib(n):
	a=(1+math.sqrt(5))/2
	b=(1-math.sqrt(5))/2
	return int((a**n-b**n)/(a-b))

Bei n>72 bekomme ich einen Rundungsfehler und bei n>1472 einen OverflowError: (34, 'Numerical result out of range').
Gibt es die Möglichkeit mit unbegrenzt genauen Float werten zu rechnen? Oder zumindest höherer Genauigkeit?
Vll. am besten mit variabler Genauigkeit, je nachdem wie groß mein n ist.
Der OverflowError ist schätze ich mal auch ein Float Problem, da ich mMn schon mit größeren Integern gerechnet habe. Was kann ich da machen?

MfG Tompazi

[DasIch]

Dafür gibt es decimal.

[Sirius3]

Nein! Unbegrenzt genaue Floats gibt es nicht, es sei denn Du hast unbegrenz Zeit und unbegrenz Speicher.
Für alles andere gibt es decimal.

[BlackJack]

@Tompazi: Zwischen rekursiv und geschlossener Formel gäbe es noch die Möglichkeit das ganze einfach iterativ zu schreiben.

[schaeffkoch]

um den zahlenraum etwas zu erweitern hilft auch numpy.float96, aber wie schon erwähnt unbegrenzte floats gibt es nicht.

[Tompazi]

Danke, aber:
bei precision 100 stimmen die Zahlen bis n=465
bei 200 bis n=944
und bei 201 nur bis n=5
Warum? Kann ich irgendwie noch genauer rechnen?

Code: Alles auswählen

from decimal import *
def fibd(n):
	getcontext().prec=200
	a=(Decimal(1)+Decimal(5).sqrt())/Decimal(2)
	b=(Decimal(1)-Decimal(5).sqrt())/Decimal(2)
	return int((a**n-b**n)/(a-b))

Iterativ ist in diesem Fall natürlich schneller und genauer aber ich mache das eher aus akademischen Gründen mit Formel.

[Sirius3]

schau mal Dein Ergebnis ohne int an

[schaeffkoch]

es geht auch mit dp