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

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 合作。这是我的第二次应用/实验。我真的很喜欢，但我还不知道它的一些特质。

编辑

更新脚本以反射(reflect)建议的更改和所述更改的运行时结果。通过上述更改，我现在可以在 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 优雅地处理了这个问题。看来在 crystal 中，只能由我来优雅地处理了。

Answer 1

Crystal 中的默认整数类型是 Int32，所以如果您没有显式指定整数文字的类型，您就会得到它。

特别是台词

fib_last = 0
fib_now  = 1

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

fib_last = 0u64
fib_now  = 1u64

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

编辑更新问题的答案

斐波那契定义为 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₉₄，因此您得到它“太早了”。

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