Ruby "FloatDomainError: Infinity" when calculating Fibonacci Number

Question

我计算斐波那契数（即位数）"length" 的方法在第 1474 次迭代后失败。我获得预期结果的方法可能非常笨拙，所以如果我的方法有缺陷，请告诉我。我怀疑运行在无限范围内使用块方法直到它偶然发现答案是相当浪费的，但在这个阶段它是我得到的最好的。不过我当然想做得更好。

对于小于以下数字的数字，它可以完美运行，直到达到第 1474 个数字：

49922546054780146353198579531352153533212840109029466994098142197617303359523104269471455390562835412104406019654730583800904132982935807202575490044075132631203284854890505808877430837618493577512703453928379390874730829906652067545822236147772760444400628059249610784412153766674534014113720760876471943168

此后 returns 此错误：

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 中创建了一个 无限范围 和运行一个 block 方法循环:

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.

如果您想避免该问题，则需要使用整数数学来执行此操作。 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 到 10,000 的术语），那么我建议您制作 #sequence public 并对其进行切片以使算法更快。

Ruby "FloatDomainError: Infinity" when calculating Fibonacci Number

Ruby "FloatDomainError: Infinity" when calculating Fibonacci Number

ruby

range

fibonacci

infinite