为什么这个程序会溢出？

Question

我有一个计算 ith 斐波纳契数的小 golang 程序，但是它似乎会溢出一些大数，即使数组更改为 int64 类型也是如此。为什么会这样？

package main

import "fmt"

func main() {
    fib(555) //prints a negative number

}

func fib(num int) {

    queue := []int{0, 1}

    for i := 0; i < num; i++ {
        next := queue[0] + queue[1]
        queue[0] = queue[1]
        queue[1] = next
    }

    fmt.Println(queue[len(queue)-1])

}

Answer 1

因为第555个斐波那契数是

43516638122555047989641805373140394725407202037260729735885664398655775748034950972577909265605502785297675867877570[=10]

即使是 int64 也太大了。

Answer 2

斐波那契数列变得非常大，非常快。您需要使用 math/big 包才能计算这么大的整数。翻译你的算法给我们：

queue := []*big.Int{big.NewInt(0), big.NewInt(1)}

for i := 0; i < num; i++ {
    next := new(big.Int).Add(queue[0], queue[1])
    queue[0] = queue[1]
    queue[1] = next
}

或更简洁：

for i := 0; i < num; i++ {
    queue[0].Add(queue[0], queue[1])
    queue[0], queue[1] = queue[1], queue[0]
}

https://play.golang.org/p/udIITdDPfrY

这将以 555 作为输入输出以下数字：

70411399558423479787498867358975911087747238266614004739546108921832817803452035228895708644544982403856194431208467

（这与预期的第 555 个斐波那契数相差 1，因为它的索引为 0）

为什么这个程序会溢出？

Why is this program overflowing?

integer-overflow

go