Ruby "FloatDomainError: Infinity" lors du calcul de Fibonacci Numéro

Question

Ma méthode pour calculer la "longueur" d'un nombre de fibonacci (c'est-à-dire le nombre de chiffres) échoue après la 1474ème itération. Ma façon d'obtenir le résultat escompté est probablement très maladroite, alors s'il vous plaît faites-moi savoir s'il y a une faille dans mon approche. Je soupçonne qu'il y a quelque chose d'assez inutile dans l'exécution d'une méthode de blocage à travers une gamme infinie jusqu'à ce qu'elle trébuche sur la réponse, mais à ce stade, c'est le meilleur que j'ai. Je voudrais certainement faire mieux cependant.

Pour les nombres inférieurs à celui ci-dessous, il fonctionne parfaitement, jusqu'à ce qu'il soit au nombre 1474e:

49922546054780146353198579531352153533212840109029466994098142197617303359523104269471455390562835412104406019654730583800904132982935807202575490044075132631203284854890505808877430837618493577512703453928379390874730829906652067545822236147772760444400628059249610784412153766674534014113720760876471943168

et retourne par la suite cette erreur:

FloatDomainError: Infinity 

Voici comment mes méthode fonctionne :

D'abord j'utilise la formule standard pour obtenir le "nième" nombre dans une séquence de fibonacci:

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

Puis-je convertir la sortie d'une chaîne et mesurer sa longueur:

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

Et puis enfin je créer une méthode gamme infinie et exécuter un bloc dans un while:

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

En Ruby, comme pour tout système à virgule flottante, il existe une valeur maximale qui peut être exprimée. Vous avez un numéro de 308 chiffres là et le maximum pour les flotteurs est Float::MAX ou 1.7976931348623157e+308.

Vous aurez besoin de faire cela avec Maths entiers si vous voulez éviter ce problème. Le système "bignum" de Ruby peut gérer des nombres de longueurs arbitraires allant jusqu'à des millions de places, mais sachez que la performance devient plutôt mauvaise plus elle est grande.

Voici un remplacement unoptimized:

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

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

    return a[-1] 
end 

Il convient de noter que votre calcul basé Float, comme avec tout avec les mathématiques à virgule flottante, est une approximation et non une valeur exacte. Ceci est absolument essentiel de se souvenir de faire des mathématiques avec des valeurs à virgule flottante. C'est très bien pour des choses comme les simulations de dynamique des fluides ou le rendu 3D où les chiffres sont assez proches. C'est pas amende pour des choses comme ceci où chaque chiffre compte, ou des situations monétaires où les erreurs de précision pourraient conduire à des milliers ou des millions de dollars en argent perdu.

Voici le numéro calculé par rapport à une force brute avec les mathématiques entier fiable:

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

Vous pouvez voir les deux valeurs divergent énormément.

Answer 2

Vous devez utiliser l'arithmétique des nombres entiers car il est capable de prendre en charge une précision infinie. Vous avez utilisé le point flottant dont la précision est limitée.

Pour accélérer les calculs, je vous recommande de mettre en cache les valeurs de la séquence.La mise en œuvre peut être aussi simple que:

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 

Vous pouvez ajouter une détection d'erreurs (par exemple en portant une erreur lors de n <= 0). Si vous souhaitez utiliser un algorithme itératif alors quelque chose comme ce qui suit devrait fonctionner:

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 

Si vous voulez travailler avec une tranche de la séquence (disons termes de 1 à 10 000) alors je vous recommande de faire #sequence public et prendre en tranches pour rendre l'algorithme plus rapide.