斐波那契问题导致算术溢出

Question

问题：用一个输入创建一个函数。返回包含斐波那契数列（从 0 开始）的数组的索引，其元素与函数的输入匹配。

  16 ~ ? def fib(n)
  17 ~ ?   return 0 if n == 0
  18   ? 
  19 ~ ?   last    = 0u128
  20 ~ ?   current = 1u128
  21   ? 
  22 ~ ?   (n - 1).times do
  23 ~ ?     last, current = current, last + current
  24   ?   end
  25 + ? 
  26 + ?   current
  27   ? end
  28   ?
  60   ? def usage
  61   ?   progname = String.new(ARGV_UNSAFE.value)
  62   ? 
  63   ?   STDERR.puts <<-H
  64   ?   #{progname} <integer>
  65   ?     Given Fibonacci; determine which fib value would
  66   ?     exist at <integer> index.
  67   ?   H
  68   ? 
  69   ?   exit 1
  70   ? end
  71   ? 
  72   ? if ARGV.empty?
  73   ?   usage
  74   ? end
  75   ? 
  76   ? begin
  77 ~ ?   i = ARGV[0].to_i
  78 ~ ?   puts fib i
  79   ? rescue e
  80   ?   STDERR.puts e
  81   ?   usage
  82   ? end

我对这个问题的解决方法一点也不优雅，我是在凌晨 2 点在我很累的时候做的。所以我不是在寻找更优雅的解决方案。我很好奇的是，如果我使用大于 45 的输入运行生成的应用程序，那么我会看到Arithmetic overflow. 我想我的变量类型有问题。我在 Ruby 中运行了它，它运行得很好，所以我知道这不是硬件问题......

有人可以帮我找出我做错了什么吗？我也在挖。我这周刚开始与 Crystal 合作。这是我的第二个应用程序/实验。我真的很喜欢，但我还没有意识到它的一些特质。

编辑

更新了脚本以反映所述更改的建议更改和运行时结果。通过上述更改，我现在可以在 45 号以上成功运行该程序，但最多只能运行 90 秒左右。所以这很有趣。我将遍历这个并查看我可能需要添加额外的显式转换的位置。在启动时更改类型并没有“坚持”整个运行时，这似乎非常不直观，我首先尝试过，但失败了。对我来说有些事情没有意义。

原始结果

$ crystal build fib.cr
$ ./fib 45
1836311903
$ ./fib 46
Arithmetic overflow
$ ./fib.rb 460
985864329041134079854737521712801814394706432953315\
510410398508752777354792040897021902752675861

最新结果

$ ./fib 92
12200160415121876738
$ ./fib 93
Arithmetic overflow
./fib <integer>
  Given Fibonacci; determine which fib value would
  exist at <integer> index.

编辑^2

现在也决定可能ARGV[0]是问题所在。所以我把电话改成了f()：

$ crystal build fib.cr
$ ./fib 45
1836311903
$ ./fib 46
Arithmetic overflow
$ ./fib.rb 460
985864329041134079854737521712801814394706432953315\
510410398508752777354792040897021902752675861

并添加了一个调试打印来显示正在使用的变量的类型：

$ ./fib 92
12200160415121876738
$ ./fib 93
Arithmetic overflow
./fib <integer>
  Given Fibonacci; determine which fib value would
  exist at <integer> index.

p: UInt64       fib_now: UInt64 fib_last: UInt64        fib_hold: UInt64        i: UInt64
Arithmetic overflow
./fib <integer>
  Given Fibonacci; determine which fib value would
  exist at <integer> index.

编辑^3

在 Jonne 的错误修复解决方案后更新了最新代码。原来的问题是，即使使用 128 位无符号整数，我也达到了结构的限制。Ruby 优雅地处理了这个问题。似乎在水晶中，我可以优雅地处理它。

Answer 1

Crystal 中的默认整数类型是Int32，因此如果您没有明确指定整数文字的类型，您就会明白。

特别是线条

fib_last = 0
fib_now  = 1

将变量转换为有效类型Int32。要解决此问题，请确保指定这些整数的类型，因为您不需要负数，UInt64这里似乎最合适：

fib_last = 0u64
fib_now  = 1u64

还要注意我在这里使用的文字语法。您的0.to_i64's 创建一个In32然后一个Int64。编译器将足够聪明，可以在发布版本的编译时进行这种转换，但我认为只使用文字语法更好。

编辑对更新问题的回答

Fibonacci 被定义为 F ₀ = 0, F ₁ = 1, F _n = F _n-2 + F _n-1，所以 0, 1, 1, 2, 3, 5. 你的算法差一。对于给定的 n > 1，即 0, 1, 2, 3, 5，它计算 F _n+1，换句话说，它基本上跳过 F ₂。

这是一个正确的方法：

def fib(n)
  return 0 if n == 0

  last = 0u64
  current = 1u64

  (n - 1).times do
    last, current = current, last + current
  end

  current
end

这正确地为 F ₉₂提供 7540113804746346429和 12200160415121876738 为 F ₉₃。然而，它仍然溢出 F ₉₄因为那将是 19740274219868223167 它大于 2 ⁶⁴ = 18446744073709551616，所以它不适合UInt64. 再次澄清，您的版本在被要求提供 F ₉₃时会尝试计算 F ₉₄，因此您“为时过早”得到它。

因此，如果您想支持为 n > 93计算 F _n，那么您需要冒险进入实验Int128/UInt128支持或使用BigInt.