計算斐波納契數時Ruby「FloatDomainError：Infinity」

Question

我的計算斐波納契數的「長度」（即數位數）的方法在第1474次迭代後失敗。我獲得理想結果的方式可能非常笨拙，請讓我知道我的方法是否存在缺陷。我懷疑在無限範圍內運行阻塞方法會有些浪費，直到它在整個答案中絆倒，但在這個階段，這是最好的。我當然想要做得更好。

對於除下一個較小的數字，它完美的作品，直到它到達第1474號：

49922546054780146353198579531352153533212840109029466994098142197617303359523104269471455390562835412104406019654730583800904132982935807202575490044075132631203284854890505808877430837618493577512703453928379390874730829906652067545822236147772760444400628059249610784412153766674534014113720760876471943168

，然後返回此錯誤：

FloatDomainError: Infinity 

這裏是如何我的方法作品：

首先我使用標準公式獲得斐波納契數列中的「nth」數字：

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

然後我的輸出轉換爲字符串，並測量其長度：

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

然後終於我創建無限範圍和運行內部的塊方法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

在Ruby中，與任何浮點系統一樣，可以表示一個最大值。你有一個308位數字，浮動的最大值是Float::MAX或1.7976931348623157e+308。

如果你想避免這個問題，你需要用Integer數學來做到這一點。 Ruby的「bignum」系統可以處理高達數百萬個位置的任意長度的數字，但要注意，性能確實會越差越大。

下面是一個未經優化的更換：

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

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

    return a[-1] 
end 

值得一提的是您的基於浮動的計算，與任何與浮點運算，是近似而不是精確值。無論何時用浮點值進行數學運算，這都是至關重要的。對於流體動力學模擬或足夠接近的3D渲染等情況，這是很好的。對於像這樣的事情，每個數字都是重要的，或者是精確度錯誤可能導致成千上萬或數百萬美元的貨幣損失的貨幣情況，它就是而不是。

這裏就是你比計算出的號碼的單蠻力強行與可靠的整數運算：

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

你可以看到兩個值偏離瘋狂。

Answer 2

您需要使用整數算術，因爲它能夠支持無限精度。您使用了精度有限的浮點。

爲了加速計算，我建議您緩存序列的值。實現可以是簡單的：

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 

您可以添加一些錯誤檢測（例如提高一個錯誤，當n <= 0）。如果您想使用的迭代算法，然後像下面應該工作：

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 

如果你想與序列的片工作（比如從1到10000項），那麼我建議你做#sequence公開，並採取切片，使算法更快。