Ruby "FloatDomainError: Unendlichkeit" bei der Berechnung von Fibonacci Nummer

Question

Meine Methode zur Berechnung der "Länge" einer Fibonacci-Nummer (d. H. Anzahl der Ziffern) schlägt nach der 1474. Iteration fehl. Meine Art, das gewünschte Ergebnis zu erzielen, ist wahrscheinlich sehr ungeschickt. Bitte lassen Sie mich wissen, ob es einen Fehler in meinem Ansatz gibt. Ich vermute, dass es etwas ziemlich Verschwenderisches gibt, wenn man eine Blockmethode über eine unendliche Bandbreite laufen lässt, bis sie über die Antwort stolpert, aber in diesem Stadium ist es das Beste, was ich habe. Ich würde es sicherlich gerne noch besser machen.

Für Zahlen kleiner als die unten, es funktioniert perfekt, bis er an die 1474. Nummer bekommt:

49922546054780146353198579531352153533212840109029466994098142197617303359523104269471455390562835412104406019654730583800904132982935807202575490044075132631203284854890505808877430837618493577512703453928379390874730829906652067545822236147772760444400628059249610784412153766674534014113720760876471943168

Und danach gibt diesen Fehler zurück:

FloatDomainError: Infinity 

Hier ist, wie meine Methode funktioniert :

Zuerst verwende ich die Standardformel, um die "nth" Zahl in einer Fibonacci-Folge zu erhalten:

def fibonacci_index(n) 
    ((1/Math.sqrt(5)) * ((1 + Math.sqrt(5))/2) ** (n + 1)).round(0) 
end 

Dann konvertiere ich die Ausgabe in einen String und messen seine Länge:

def fibonacci_index_length(n) 
    fibonacci_index(n).to_s.length 
end 

Und dann schließlich erstelle ich eine unendliche Reihe und einen Block Methode innerhalb einer while-Schleife laufen:

def find_fibonacci_index_by_length(integer) 

    # Range to infinity because I don't want to 
    # limit the size of the numbers I work with 
    infinity = 1.0/0.0 
    range = (1..infinity) 

    # while loop to run through the range 
    running = true 

    while running 
    range.each do |n| 

     f_index = n + 1 
     f_number = fibonacci_index(n) 
     f_length = fibonacci_index_length(n) 

     if fibonacci_index_length(n) == integer && fibonacci_index(n) != 1 

     puts "f_index: #{f_index}" 
     puts "f_number: #{f_number}" 
     puts "f_length: #{f_length}" 

     running = false 

     # This breaks from the block 
     return f_index 

     elsif fibonacci_index_length(n) == integer && fibonacci_index(n) == 1 

     running = false 
     return 1 

     else 
     # puts "Still looking, number is #{fibonacci_index(n)}" 
     puts "Still looking, Fibonacci index: #{f_index}" 
     puts f_number 
     end 
    end 
    end 
end 

Answer 1

In Ruby gibt es wie bei jedem Gleitkomma-System einen maximalen Wert, der ausgedrückt werden kann. Sie haben dort eine 308 stellige Nummer und das Maximum für Floats ist Float::MAX oder 1.7976931348623157e+308.

Sie müssen dies mit Ganzzahlmathematik tun, wenn Sie dieses Problem vermeiden möchten. Rubys "Bignum" -System kann beliebig viele Zahlen bis zu Millionen von Stellen verarbeiten, aber sei dir bewusst, dass die Leistung umso schlechter wird, je größer sie werden.

Hier ist ein nicht optimierten Ersatz:

def fibonacci_index(n) 
    a = [ 1, 1 ] 

    while (a.length < n) 
    a << (a[-1] + a[-2]) 
    end 

    return a[-1] 
end 

Es ist erwähnenswert, dass Ihre Float-basierte Berechnung, wie mit allem, was mit Punkt Mathe schwimmt, ist eine Annäherung und kein exakter Wert. Dies ist unbedingt zu beachten, wenn Sie mit Fließkommawerten rechnen. Dies ist gut für Dinge wie Strömungssimulationen oder 3D-Rendering, bei denen nahe genug zählt. Es ist nicht gut für Dinge wie diese, wo jede Ziffer zählt, oder monetäre Situationen, wo Präzisionsfehler zu Tausenden oder Millionen von Dollar in verlorenes Geld führen könnte.

Hier ist die Zahl, die Sie im Vergleich zu berechnenden die eine Brute-Zwangs mit zuverlässigen integer math:

4992254605477767835147644879936483062623238506802202927705709236175156181701079... 
4992254605478014635319857953135215353321284010902946699409814219761730335952310... 
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 

Sie können die beiden Werte sehen wild divergieren.

Answer 2

Sie müssen Integer-Arithmetik verwenden, da sie unendliche Genauigkeit unterstützen kann. Sie haben Gleitkommazahlen verwendet, deren Genauigkeit begrenzt ist.

Um die Berechnungen zu beschleunigen, empfehle ich, die Werte der Sequenz zwischenzuspeichern.Die Implementierung kann so einfach sein wie:

class RecursiveFibonacci 
    def initialize 
    @cache = { 1 => 1, 2 => 2 } 
    end 

    def [](n) 
    @cache[n] ||= self[n - 2] + self[n - 1] 
    end 
end 

fibonacci = Fibonacci.new 
fibonacci[6] #=> 13 

Sie können einige Fehlererkennung hinzuzufügen (zum Beispiel Erhöhung einen Fehler, wenn n <= 0). Wenn Sie einen iterativen Algorithmus verwenden möchten, dann sollten etwa wie folgt funktionieren:

class IterativeFibonacci 
    def [](n) 
    # Add 1 to covert the index from zero-based to one-based. 
    sequence.take(n + 1).last 
    end 

    private 

    def sequence 
    Enumerator.new do |yielder| 
     a, b = 1, 1 
     yielder << a 
     loop do 
     a, b = b, a + b 
     yielder << a 
     end 
    end 
    end 
end 

Wenn Sie mit einer Scheibe der Sequenz arbeiten wollen (sagen Begriffe von 1 bis 10.000), dann empfehle ich Ihnen #sequence machen öffentlich und nehmen Sie es in Scheiben, um den Algorithmus schneller zu machen.