Search code examples
gointeger-overflow

Why is this program overflowing?

I have a small golang program that calculates the ith fibonnaci number, however it appears to overflow for some numbers large numbers, even when the array is changed to a type of int64. Why is this happening?

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])

}
Solution

  • The Fibonacci sequence gets very large, very fast. You need to use the math/big package in order to calculate integers this large. Translating your algorithm gives us:

    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
}

    or more concisely:

    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

    Which will output the following number with 555 as the input:

    70411399558423479787498867358975911087747238266614004739546108921832817803452035228895708644544982403856194431208467

    (this is off by 1 from the expected 555th Fibonacci number, since it's 0 indexed)