Fibonacci问题导致算术溢出

Question

问题:用一个输入创建一个函数。返回包含fibonacci序列的数组的索引(从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中运行了这个，运行得很好，所以我知道这不是硬件问题.

有人能帮我找出我做错了什么吗？我也还在挖呢。我这周刚开始和克里斯托一起工作。这是我对它的第二次应用/实验。我真的很喜欢，但我还没有意识到它的一些特性。

编辑

更新的脚本，以反映建议的更改和运行时的结果从上述更改。有了上述的改变，我现在可以成功地运行程序的数字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()的调用更改为：

 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很优雅地处理了这个问题。似乎在水晶里，它是由我优雅地处理它。

Answer 1

除了整数值默认为Int32这一事实之外，我认为还应该提到一件事来解释Ruby/Crystal之间的差异。

在动态类型解释语言Ruby中，没有变量类型的概念，只有值类型。所有变量都可以保存任何类型的值。

这样，当Fixnum溢出时，它就可以透明地将其转换为幕后的Bignum。

相反，水晶是一种静态类型的编译语言，由于类型推断和类型联合，它看起来和感觉都很像Ruby，但是变量本身是类型的。

这使它能够在编译时捕获大量错误，并以类似C的速度运行类似Ruby的代码。

我认为，但不要相信我的话，水晶可以在理论上匹配Ruby的行为，但这将是更多的麻烦，而不是好。它将需要对整数的所有操作返回一个类型联合与BigInt，在这一点上，为什么不离开原语类型，并在必要时直接使用大整数。

长话短说，如果您需要处理一个UInt128所能容纳的非常大的整数值，那么require "big"并声明相关变量BigInt。

编辑:对于极端情况，请参见here，显然BigInt也会溢出(我从来不知道)，但是有一个简单的解决方法。