Fibonacci-Berechnung

[Bruno_Haller_81c15f]

Hallo,

ich habe es im Brett Programmierung schon versucht, aber vielleicht bin ich hier besser aufgehoben.

Wie laesst sich SCHNELL eine sehr grosse Fibonacci-Zahl berechnen (Ziel: die 5Millionste)?

Ich bin im Internet mehrfach auf die Formel

Phi = (Wurzel(5) + 1) / 2
Fib(x) = Phi^x / Wurzel(5)

gestossen, allerdings habe ich damit ein Problem, weil ich die Zahl natürlich mit dem Computer berechnen will… und bei einem Exponenten in Millionengrösse setzt sich eine kleine Ungenauigkeit extrem schnell fort. Schon bei 1000 habe ich eine total ungenaue Zahl herausbekommen.

Gibt es andere Algorithmen, die ohne Fliesskommazahlen auskommen oder hat einer evtl. sogar einen Quellcode.

Danke
Bruno

[Anonym]

Ansatz (1.Teil)
Hallo!

So wie ich das sehe, brauchst Du nur genaue Rechenvorschriften und -Methoden für die Multiplikation (Potenzierung mit x), das Ziehen der Quadratwurzel, die Division und die Addition. Wie Du sicher weißt, ist mit 32 oder 64 Bit langen Variablen, wie sie halbwegs moderne Betriebssysteme bieten, nicht viel aufgeführt. Daher gilt es, eigene Verfahren und Algorithmen zu finden, die mehr Stellen in den Operanden „verkraften“.

Ich gehe im folgenden von Grundkenntnissen in der Programmierung mit einer gängigen Hochsprache aus.

Man bastelt sich einen Datentyp, der alle Stellen, welche dargestellt werden sollen, aufnehmen soll (also etwa eine Dezimalstelle/Byte oder weniger speicherintensiv eine Dezimalstelle/(4 bit)).
Jetzt muß man nur noch die Rechenoperationen mit diesen langen Datentypen aus den Grundoperationen des Prozessors „zusammenstöpseln“.

Addieren ist wohl das einfachste: Einfach ausführen, was man in der Volksschule tat, wenn es darum ging, 2 Zahlen zu addieren.

Multiplizieren von 2 n-stelligen Zahlen nach der Schulmethode ist schon aufwändiger: Es sind n*n=n^2 Multiplikationen und eine Addition nötig. Also: Die Multiplikation doppelt langer Zahlen dauert 4 mal so lange. Ist n entsprechend groß, ist der Rechenaufwand gigantisch.
Abhilfe schafft die Multiplikation nach Karatsuba:
Zerlegen wir die zu multiplizierenden 2n-stelligen Zahlen u und v in eine obere und untere Hälfte von je n Stellen, so ergibt sich mit u=(10^n)u1+u0 und v=(10^n)*v1+v0:

uv=((10^2n)+(10^n))*u1*v1+(10^n)*(u1-u0)*(v0-v1)+((10^n)+1)*u0v0

Wir haben also 3 Teilmultiplikationen und 6 Additionen, was viel schneller geht als n^2 Multiplikationen und 1 Addition wie bei der Schulmethode. Die 10^n und 10^2n können einfach durch Dezimalshifts erzeugt werden.

Dividieren von u/v läßt sich mit der Newtoschen Näherung zur Kehrwertberechnung durchführen:

u/v=(1/v)u, also eine Kehrwertbildung und eine Multiplikation.

Iterationsvorschrift:

Anfangswert: x0=1/v, x(k+1) steht für x mit Index k+1:

x(k+1)=x(k)+x(k)(1-v*x(k))

Dies wird solange durchgeführt, bis der Ausdruck x(k)(1-v*x(k)) im Rahmen der Rechengenauigkeit 0 ist.

Das Berechnen der Quadratwurzel geht mit einer weiteren Newtonschen Näherung:

Zunächst berechnet man den Kehrwert von SQRT(d) in der Form 1/SQRT(d) durch folgendes Iterationschema (Anfangswert: x0=1/SQRT(d)):

x(k+1)=x(k)+x(k)*(1-d*x(k)*x(k))/2

Dies wird solange durchgeführt, bis der Ausdruck x(k)*(1-d*x(k)*x(k))/2 im Rahmen der Rechengenauigkeit 0 ist.
Abschließend multipliziert man das Resultat noch mit d, um SQRT(d) zu erhalten.

Also damit solltest Du den Algorithmus für die Fibonacci-Zahlen hinkriegen.

Allerdings würde ich persönlich die Fibonacci-Zahlen gemäß ihrer Definition berechnen, was nur Additionen erfordert, die letzten 2 Drittel meiner seitenweisen Schreiberei also gar nicht erfordert:

F(n+2)=F(n+1)+F(n)

In Worten: Jede nachfolgende Fibonacci-Zahl ist die Summer ihrer beiden Vorgänger, wobei mit 0 und 1 begonnen wird.

Also: F(n)=0,1,1,2,3,5,8,13,21,34,…

Grüße und Glück auf

Safog

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

[Bruno_Haller_81c15f]

Alles schön und gut
Den Algorithmus der Multiplikation durch Bitshifts etc. haben wir in der Berufsakademie mal durchgesprochen, den würde ich anwenden.
Aber du redest viel von Näherung . Die Berechnung muss aber genau sein.
Ich hab wie gesagt mit besagter Formel, schon beim Exponenten 1000 eine riesige Ungenauigkeit reingekriegt, weil so genau lässt sich eine Zahl vermutlich gar nicht im Rechner darstellen, dass sie beim Exponieren noch exakt bleibt.

F(n+2)=F(n+1)+F(n)

Oh Gott Das ist ja sozusagen der rekursive Ansatz, da versagt ein normaler PC schon bei zweistelligen Fibonaccis
Das kannste den Hasen geben, hehe

Danke Bruno

[Bruno_Haller_81c15f]

Ergänzung
Mein problem mit der Formel des „golden ratio“ ist das Phi.

Phi ist irgendwas 1,6…

beim Potenzieren mit 1000000 z.b. macht es halt einen Riesenunterschied ob der Rechner an der zigten Nachkommastelle jetzt 1,6…1 oder 1,6…2 stehen hat.

Deswegen glaub ich, ich komm so nicht weiter.

[Martin]

Anderer Ansatz
Hi Bruno,

F(n+2)=F(n+1)+F(n)

Oh Gott Das ist ja sozusagen der
rekursive Ansatz, da versagt ein normaler
PC schon bei zweistelligen Fibonaccis
Das kannste den Hasen geben, hehe

ich kann Dein vernichtendes Urteil über die Rekursionsformel nicht nachvollziehen. Deren Vorteil liegt doch auf der Hand: Da Du nur Ganzzahlen (riesengroße, versteht sich) addieren mußt, hast Du von Haus aus keine Rundungsfehlerprobleme zu befürchten, und die Addition geht auch vergleichsweise schnell. Was willst Du denn mehr?

Zum Algorithmus. Sind u, v, w Riesen-Ganzzahlen und n der Index der gewünschten Fibonaccizahl (wenn z. B. die 689ste F.zahl gewünscht ist --> n = 689), dann lautet derselbe:

u := 1;
v := 1;
w := 1;

FOR i := 3 TO n DO
 begin
 w := w + u;
 u := v;
 v := w
 end;

Die großen Zahlen u, v, w sind vom Typ „TBigNumber“, der definiert ist als

TYPE TBigNumber = ARRAY[0..N\_DIV\_9] OF LONGINT;

Die Konstante N_DIV_9 ist ein Neuntel der gewünschten Stellenanzahl; wird z. B. N_DIV_9 auf 12000 gesetzt, kann eine TBigNumber-Variable Werte bis maximal 9 * 12000 = 108000 Stellen aufnehmen.

Das „ein Neuntel“ kommt daher, daß die Rechnerei zweckmäßigerweise zur Basis 10^9 (Konstante „NumBase“) erfolgt, denn das ist die größte Zehnerpotenz, die eine LONGINT-Variable noch aufnehmen kann. Diese Basis zu wählen hat den Vorteil, daß das Resultat dann als in 9-Stellen-Blöcken aufgeteilte Dezimalzahl interpretiert werden kann (jedes Element des Arrays repräsentiert einen Block).

Das Auf-Eins-Setzen einer Variablen r (r = u, v, w) ist denkbar einfach:

FOR k := 0 TO (N\_DIV\_9)-1 DO
 begin
 r[k] := 0
 end;
r[(N\_DIV\_9)-1] := 1

Nun fehlt noch die Addition „w := w + u“. Die ist wie folgt zu realisieren:

FOR k := (N\_DIV\_9)-1 DOWNTO 0 DO
 begin
 w[k] := w[k]+u[k];
 IF (w[k]\>=NumBase) THEN
 begin
 w[k] := w[k]-NumBase;
 Inc(w[k-1])
 end
 end;

Der Block „IF (w[k]>=NumBase) THEN…“ ist die Überlaufprüfung und -behandlung.

Die Erklärung, wie das Ergebnis in eine Folge von z. B. 60 Zeichen langen Strings umgewandelt wird, die dann in eine Datei geschrieben werden, spare ich mir.

Wenn Du Dir jetzt mit diesen Infos selbst ein Proggi stricken willst, habe ich noch als Tip für Dich, daß N_DIV_9 = 12000 für die 500’000. Fibonaccizahl ausreicht (die hat ca. 100’000 Stellen). Mein Delphi-Proggi benötigt dafür auf ner P II/333-Maschine knapp 9 min.

Mit freundlichem Gruß
Martin

[Bruno_Haller_81c15f]

Das ist ja iterativ… ich meinte du willst den rekursiven Ansatz benutzen nach dem Motto

int fib(int wert)
{
 if (wert = 1) return 1;
 else return (fib(wert-1) + fib(wert-2));
}

Das gibt bereits ab so ca. Fib(30) den Geist auf nem normalen rechner auf

Ok, dein Ansatz ist vielleicht doch ganz gut hehe, aber im Moment hab ich da eher was mit Matrizenmultiplikation im Auge, hab schon irgendwo eine interessante Formel gefunden, jetzt muss mir nur noch jemand im andren Thread antworten wie die schnelle Potenzierung geht…

[Anonym]

Alles schön und gut
Den Algorithmus der Multiplikation durch
Bitshifts etc. haben wir in der
Berufsakademie mal durchgesprochen, den
würde ich anwenden.
Aber du redest viel von Näherung . Die
Berechnung muss aber genau sein.
Ich hab wie gesagt mit besagter Formel,
schon beim Exponenten 1000 eine riesige
Ungenauigkeit reingekriegt, weil so genau
lässt sich eine Zahl vermutlich gar nicht
im Rechner darstellen, dass sie beim
Exponieren noch exakt bleibt.

Ich weiß nicht, ob Du Dir mein Posting angeschaut hast, oder nicht, auf alle Fälle scheinst Du nicht ganz verstanden zu haben, dass ich die Potenzierung als Multiplikation von langen Datentypen vorgeschlagen habe und dazu den speziellen Multiplikationsalgorithmus verwenden würde.

Zu den Näherungen: Durch die Möglichkeit der Genauigkeitskontrolle kannst Du doch jederzeit festlegen, wie genau die Rechnung werden soll, was soll also die Bemerkung mit „Die Berechnung muss aber genau sein“?

F(n+2)=F(n+1)+F(n)

Oh Gott Das ist ja sozusagen der
rekursive Ansatz, da versagt ein normaler
PC schon bei zweistelligen Fibonaccis

Auch eine Cray T90™ versagt, wenn man einen Schimpansen davorsetzt.

Wenn Du den Ansatz so aufziehst wie in der Antwort zu Martins Posting, wird die Berechnung mit Sicherheit länger dauern als Dein Studienabschluss noch Zeit benötigt.
Nicht die Rechenvorschrift ist das Problem, sondern viel mehr ihre Implementierung.

Es reicht doch vollkommen, die 2 letzten Fibonaccizahlen im Speicher zu halten und für die folgende zu addieren. Du kannst doch nicht allen Ernstes annehmen, die Sache rekursiv machen zu können.
Auch Deine Matrizenmultiplikation erfordert mindestens so viele Multiplikationen wie die Ordnung der Fibonacci-Zahl, welche Du berechnen willst. Der normale Additionsansatz benötigt ebensoviele Operationen, nur dass es diesmal Additionen sind. Meinem ersten Posting ist unschwer zu entnehmen, was das für einen Zeitvorteil bedeutet.

Das kannste den Hasen geben, hehe

Habs mit keinem Hasen, sonder einem PIII 600 und simpelstem C++ probiert. Hier die Berechnungszeiten mit „rekursivem Ansatz“:

F(5.000.000): 8,1 s
F(10.000.000): 17,4 s
F(20.000.000): 36,7 s

Zum Beweis: Das 1.044.937 Stellen lange F(5.000.000) beginnt mit

7108285972058527236971171956172153220435122490862477880…

und endet mit

…514734798469045853083449528884664806936147375182913317404393849453125

Aber vielleicht ist die Methode ja wirklich für Hasen und nicht für Brunos?

Wurde der Rekord Deiner Vorgänger eigentlich auch mit Grundlagenwissen aus einschlägigen News-Groups aufgestellt???

Grüße

Der nähernde Safog

[Bruno_Haller_81c15f]

Sorry für meien Überheblichkeit aber du hasts mir ja auch gleich reindrücken müssen *g*

8,1sek das ist natürlich echt genial,
würde mich echt brennend interessieren das Programm.

Kannst du es mir mailen oder ist das top secret

[Bruno_Haller_81c15f]

bin gespannt…
…wie du das realisiert hast.

Ich hab das soeben mal schnell runtergehackt.

Mein Algorithmus taugt garantiert nix, auf jeden Fall dauert die 100000. schon gut 2 Minuten

Bruno

[Martin]

Hi Safog,

Auch Deine Matrizenmultiplikation
erfordert mindestens so viele
Multiplikationen wie die Ordnung der
Fibonacci-Zahl, welche Du berechnen
willst.

da muß ich Dir widersprechen. Die 32. Potenz von x beispielsweise läßt sich wegen

x^32 = ((((x^2)^2)^2)^2)^2

mit nur 5 Multiplikationen berechnen:

FOR i := 1 TO 5 DO
begin
 x := x\*x
end;

Etwas allgemeiner läßt sich x^N wobei N = 2^n, n natürl. Zahl, mit n Multiplikationen berechnen, was einer Komplexität von O(log2(N)) entspricht.

Wenn Du die Matrix

((0,1),
(1,1))

zur N-ten Potenz erhebst, dann erhälst Du die Matrix

((N-1-te Fibonaccizahl, N-te Fibonaccizahl),
(N-te Fibonaccizahl, N+1-te Fibonaccizahl)).

Alle „Zwischen-Matrizen“ haben dabei wegen der Beziehung „N+1-te FZ = N-1-te FZ + N-te FZ“ (FZ-Definition) die Struktur

((a, b),
(b, a+b))

Das Quadrat dieser Matrix läßt sich einfach ausrechnen. Es ist

((c, d),
(d, c+d))
mit c = a^2 + b^2 und d = 2ab + b^2

Das heißt aber: Jeder Quadrierungsschritt erfordert genau 3 Multiplikationen (a*a, b*b und a*b).

Ich habe daraus folgenden Algorithmus abgeleitet (von dessen Funktionsfähigkeit ich mich auch überzeugt habe ):

a := 1;
b := 1;
FOR i := 2 TO n DO
 begin
 c := b\*b; 
 d := a\*b; 
 d := d+d; 
 d := d+c; 
 e := a\*a; 
 c := c+e; 
 a := c
 b := d
 end;
(\* b enthält jetzt die 2^n-te FZ \*)

Mit diesem Algorithmus wäre es also unter Verwendung eines Großen-Zahlen-Typs für die Variablen möglich, z. B. die 4’194’304 (= 2^22)-te Fibonaccizahl mit nicht mehr als 66 Multiplikationen auszurechnen.

In die Gesamt-Komplexität des Algorithmus geht natürlich noch die Komplexität der Operation „Multiplikation“ ein (in dem Sinne, daß die Stellenanzahl der Variablen den n-Werten angepaßt werden muß). Ich weiß leider nicht, wie es darum bestellt ist. Beträgt sie „s log s“, s = Stellenzahl, oder gar nur „log s“ - wer kann mir dazu etwas sagen?

Der normale Additionsansatz
benötigt ebensoviele Operationen, nur
dass es diesmal Additionen sind.

Ja. Um die 5’000’000. FZ zu berechnen, führt kein Weg daran vorbei, 5’000’000-1 Additionen auszuführen.

Habs mit keinem Hasen, sonder einem PIII
600 und simpelstem C++ probiert. Hier die
Berechnungszeiten mit „rekursivem
Ansatz“:

Du meinst „iterativen Ansatz“?

F(5.000.000): 8,1 s
F(10.000.000): 17,4 s
F(20.000.000): 36,7 s

*erschreck* Das sind ja Turbo-Zeiten! Geht das wirklich so fix bei Dir?

Mit freundlichem Gruß
Martin

[Anonym]

Hallo Martin,

da muß ich Dir widersprechen. Die 32.
Potenz von x beispielsweise läßt sich
wegen

x^32 = ((((x^2)^2)^2)^2)^2

mit nur 5 Multiplikationen berechnen:

Das ist natürlich klar. Ich bezog mich mehr auf den bedingungslosen Glauben Brunos an alles, was nicht Addition ist. Klar kann man auch die Multiplikation vereinfachen, auch ich habe Wege dazu aufgezeigt, die Zeit sparen helfen, wenn man mit überlangen Datentypen rechnet. Am schnellsten geht das Multiplizieren aber mit Hilfe der FFT, welche vom Rechenaufwand wie n*log(n) steigt.

Du meinst „iterativen Ansatz“?

Ich meine natürlich iterativen Ansatz, das „rekursiv“ sollte nur ein Zitat Brunos sein, welcher von Deinem Vorschlag davon überhaupt nichts gehalten hat.

*erschreck* Das sind ja Turbo-Zeiten!
Geht das wirklich so fix bei Dir?

Die reinen Rechenzeiten sind exakt so wie angegeben. Allerdings liegt dann die Fibonacci-Zahl noch im Speicher und muß erst auf dem Bildschirm ausgegeben oder in eine Datei geschrieben werden.

Als Grundlage für die langen Datentypen dient eine Eigenentwicklung meines Arbeitgebers und kann daher auch nicht
offengelegt werden. Wenn Du aber Intersse hast, kann ich Dir eine Konsolen-Binary zukommen lassen, damit Du Dich von allen Behauptungen überzeugen kannst.

Grüße Safog

[Bruno_Haller_81c15f]

Das ist natürlich klar. Ich bezog mich
mehr auf den bedingungslosen Glauben
Brunos an alles, was nicht Addition ist.

Gschwätz!
Ich glaub an alles, was schnell ist. Und eine Multiplikation kann man relativ leicht eben durch sozusagen „russisch multiplizieren“ oder wie man das nennt, mit Bitshifts etc. auf logarithmischen Aufwand bringen.

Du meinst „iterativen Ansatz“?

Ich meine natürlich iterativen Ansatz,
das „rekursiv“ sollte nur ein Zitat
Brunos sein, welcher von Deinem Vorschlag
davon überhaupt nichts gehalten hat.

Ja hab ich auch nicht, weil rekursiv für die Problemlösung nix taugt. Ich hab ja nicht behauptet dass man die Rekursion nicht umwandeln könnte in eine Iteration.

Als Grundlage für die langen Datentypen
dient eine Eigenentwicklung meines
Arbeitgebers und kann daher auch nicht
offengelegt werden.

Schaaaade Das ist das einzige was mich eigentlich interessieren würde. Der Algorithmus is klar, nur die Implementation des Datentyps lahmt bei mir so dermassen.

Wenn Du aber Intersse
hast, kann ich Dir eine Konsolen-Binary
zukommen lassen, damit Du Dich von allen
Behauptungen überzeugen kannst.

Ich hätte Interesse

Bruno

[Martin]

Hi Safog,

Am
schnellsten geht das Multiplizieren aber
mit Hilfe der FFT, welche vom
Rechenaufwand wie n*log(n) steigt.

Aha, n log n… das hätte ich so ganz intuitiv auch vermutet (ich wußte nur, daß es mit weniger als n^2 geht). Daß der Fahrer im Rennwagen der Multiplikation Fourier heißt, ist ja stark! Der Typ ist auch immer wieder für 'ne Überraschung gut . Danke für die interessante Info!

Ich meine natürlich iterativen Ansatz,
das „rekursiv“ sollte nur ein Zitat
Brunos sein, welcher von Deinem Vorschlag
davon überhaupt nichts gehalten hat.

Ich hoffe, Bruno versteht wenigstens, warum die Rekursiv-Implementierung hier völlig „daneben“ ist.

Die reinen Rechenzeiten sind exakt so wie
angegeben.

Daran hab ich auch nicht gezweifelt .

Als Grundlage für die langen Datentypen
dient eine Eigenentwicklung meines
Arbeitgebers und kann daher auch nicht
offengelegt werden. Wenn Du aber Intersse
hast, kann ich Dir eine Konsolen-Binary
zukommen lassen, damit Du Dich von allen
Behauptungen überzeugen kannst.

Nee, laß mal stecken. Bei Verwendung einer hochoptimierten Implementierung der großen Zahlen (immer soviel Daten solange wie möglich im Prozessorcache, Überträge in Registern speichern etc.), C++ statt Pascal und ner deutlich schnelleren Maschine hab ich kein Problem damit, Dir zu glauben, daß Du die Ergebnisse so schnell hast.

Viele Grüße
Martin

[Anonym]

Hallo Bruno!

Ich hätte Interesse

Gib mir einfach Deine E-Mail-Adresse (oder soll ich die hil.net-Adresse verwenden?)!

Safog

[Lutz_Lehmann]

Als Grundlage für die langen Datentypen
dient eine Eigenentwicklung meines
Arbeitgebers und kann daher auch nicht
offengelegt werden.

Schaaaade Das ist das einzige was mich
eigentlich interessieren würde. Der
Algorithmus is klar, nur die
Implementation des Datentyps lahmt bei
mir so dermassen.

Hi,

dann vielleicht PARI

http://www.parigp-home.de

oder gmp, bei jeder Linux-Distribution dabei (wegen Verschlüsselungsalgorithmen)

Ciao Lutz

[Bruno_Haller_81c15f]

Ja, [email protected]

Danke.