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

Question

问题：创建一个只有一个输入的函数。 Return 包含斐波那契数列（从 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。这是我第二次 application/experiment 使用它。我很喜欢，但我还不知道它的一些特质。

编辑

已更新脚本以反映建议的更改以及上述更改运行时间的结果。通过上述更改，我现在可以运行程序成功超过 45，但最多只能达到 90 左右。这很有趣。我将运行通过这个，看看我可能需要在何处添加额外的显式转换。似乎非常不直观的是，在启动时更改类型并没有 "stick" 整个运行时间，我首先尝试但失败了。有些东西对我来说没有意义。

原始结果

$ 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() 的调用更改为：

 62 begin                                                                                                                                                                           
 63   i = ARGV[0].to_u64.as(UInt64)                                                                                                                                                 
 64   puts f i                                                                                                                                                                      
 65 rescue e                                                                                                                                                                        
 66   STDERR.puts e                                                                                                                                                                 
 67   usage                                                                                                                                                                         
 68 end

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

22   return 0 if p == 0                                                                                                                                                            
 23                                                                                                                                                                                 
 24   puts "p: %s\tfib_now: %s\tfib_last: %s\tfib_hold: %s\ti: %s" % [typeof(p), typeof(fib_now), typeof(fib_last), typeof(fib_hold), typeof(i)]                                    
 25   loop do

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 优雅地处理了这个问题。看来在crystal，还是得靠我优雅的处理了。

Answer 1

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

特别是台词

fib_last = 0
fib_now  = 1

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

fib_last = 0u64
fib_now  = 1u64

另请注意我在此处使用的文字语法。您的 0.to_i64 创建了一个 In32，然后从中创建了一个 Int64。编译器足够聪明，可以在发布版本的编译时进行这种转换，但我认为只使用文字语法更好。

编辑更新问题的答案

Fibonacci 定义为 F₀ = 0，F₁ = 1，F_n = F_n-2 + F_n-1, 所以 0, 1, 1, 2, 3, 5. 你的算法差了一个。它为给定的 n > 1 计算 F_n+1，换句话说，0、1、2、3、5，换句话说，它基本上跳过 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，为 F₉₃ 正确给出了 12200160415121876738。但是对于 F₉₄ 它仍然会溢出，因为那将是 19740274219868223167，它大于 2⁶⁴ = 18446744073709551616，所以它不适合 UInt64。再次澄清一下，您的版本在被要求计算 F₉₃ 时尝试计算 F₉₄，因此您得到了 "too early"。

所以如果你想支持计算 F_n for n > 93 那么你需要冒险进入实验 Int128/UInt128 支持或使用BigInt.

Answer 2

除了整数文字默认为 Int32.

之外，我认为还应该提到一件事来解释 Ruby/Crystal 的区别。

在Ruby动态类型解释型语言中，没有变量类型的概念，只有值类型。所有变量都可以保存任何类型的值。
这允许它在 Fixnum 溢出时在幕后透明地将 Bignum 转换为 Bignum。

Crystal 相反是一种静态类型的编译语言，由于类型推断和类型联合，它看起来和感觉像 Ruby，但变量本身是类型化的。
这允许它在编译时捕获大量错误，并以类似 C 的速度捕获类似运行 Ruby 的代码。

我认为，但不要相信我的话，Crystal 理论上可以匹配 Ruby 的行为，但它会麻烦多于好处。它需要对整数的所有操作 return 与 BigInt 的类型联合，在这一点上，为什么不单独保留基本类型，并在必要时直接使用大整数。

长话短说，如果您需要使用超出 UInt128 可以容纳的非常大的整数值，require "big" 并声明相关变量 BigInt.

编辑：另见 here 极端情况，显然 BigInts 也会溢出（我从来不知道）但有一个简单的补救措施。

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

Fibonacci problem causes Arithmetic overflow

crystal-lang