algorithm - Golang 斐波那契计算出现关闭

Question

我目前有以下用于斐波那契计算的代码。我正在尝试计算大数，但一旦达到 100，计算就会停止。对于 fib(100)，我的代码返回 3736710778780434371，但是当我查看其他来源时，它告诉我正确的计算应该是 354224848179261915075。是我的代码有问题还是与我的计算机硬件或其他问题有关？

package main
import "fmt"

func fib(N uint) uint{


  var table []uint
  table = make([]uint, N+1)
  table[0] = 0
  table[1] = 1


  for i := uint(2); i <= N; i += 1 {

     table[i] = table[i-1] + table[i-2]


  }

  return table[N]

}

func main() {
   fmt.Println(fib(100))
}

Answer 1

您遇到了整数溢出!您只能使用大小不超过 uint 的 uint 进行计算；一旦你超出了它的界限，它就会(默默地)再次回绕。

在您的例子中，uint 看起来好像是 64 位长。 (它的大小取决于您运行的平台。)这意味着您将能够存储最多 2⁶⁴-1 的值。如果您再添加一个，它会回到 0，并且不会返回错误。

如果您将得到的答案和正确答案转换为十六进制，那么您会发现情况确实如此。你结束了

  33DB76A7C594BFC3

正确答案是

1333DB76A7C594BFC3

请注意，就目前而言，您的答案是正确的……只是还不够深入。您只得到了答案的低 64 位；你错过了其他 13*2⁶⁴。

要更正它，您需要使用 Package big 中的任意大小的整数，而不是 uint。