一尘不染

Golang Fibonacci计算出现

go

我目前在斐波那契计算中使用以下代码。我正在尝试计算大数,但是一旦达到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))
}

阅读 259

收藏
2020-07-02

共1个答案

一尘不染

您正在遇到整数溢出!您最多只能使用uint的大小进行计算uint;一旦您超越了它的界限,它将(无声地)再次绕回原处。

在您的情况下,看起来a的uint长度为64位。(其大小取决于您所运行的平台。)这意味着您最多可以存储2 64
-1的值。如果再添加一个,它将回零,并且不会返回错误。

如果将得到的答案和正确的答案转换为十六进制,那么您会发现情况确实如此。你最终以

  33DB76A7C594BFC3

正确的答案是

1333DB76A7C594BFC3

请注意,就目前而言,您的答案是正确的……只是远远不够。您只得到答案的低64位。您错过了其他13 * 2 64。

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

2020-07-02