W
Worum geht es hier eigentlich?
a) sollst du versuchen, eine eigene BigInt-Implementierung zu erstellen? Dann abstrahiere das in eigene Operationen. Insbesondere scheinst du ja mit int-Arrays die Ziffern nachbilden zu wollen. Abstrahiere die entsprechenden Operationen in Funktionen, also zum Beispiel in eine Funktion bigint_add(a, b), die dir a += b berechnet. Überlege dir auch sinnvolle Typen. Ein Array von int erscheint nicht sinnvoll, wenn jedes Array-Element nur eine Ziffer enthalten soll - dann brauchst du nicht so einen großen Datentyp wie int.
b) sollst du eine fertige Implementierung von BigInt verwenden? Der schnellste Weg, um zur n-ten Fibonacci-Zahl zu gelangen, geht über das Berechnen von [1110]n\left[\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}\right]^n[1110]n, siehe auch https://www.youtube.com/watch?v=QIHy8pXbneI&t=2107s (Video ist allerdings für C++ und mit Templates - die generelle Idee passt aber in jeder Sprache). Und dann kannst du schnell ne binäre Suche machen.
c) Du kannst mit Binets Formel die n-te Zahl direkt berechnen: Fn=(1+52)n−(1−52)n5F_n = \frac{ (\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n}{\sqrt 5}Fn=√5(21+√5)n−(21−√5)n (hoffe, das passt so...) - und rückwärts kannst du aus einer Zahl dann auch nnn bestimmen - wenn du groß genuge Floatingpoint-Operationen hast. Problem: das IEEE double kann nicht mit 1e1000 rechnen. => Du musst also erst den log bilden und nie mit 1e1000 rechnen. Die Näherung (1000 + log(sqrt(5))/log(10)) / log((1+ sqrt(5)) / 2)*log(10) = 4786.6... ist schon fast richtig. Dabei habe ich angenommen, dass der Term (1−52)n≈0(\frac{1-\sqrt 5}{2})^n \approx 0(21−√5)n≈0 für große nnn.
d) Irgendeine andere Lösung, die ausnutzt, dass nicht die Fibonaccizahl selbst, sondern nur der Index gesucht wird.
Du kannst das Ergebnis übrigens leicht mit Wolframalpha testen:
Log(10, fibonacci(4787)) liefert 1000.07...., wärend bei 4786 nur 999.86... rauskommt.
