Golang Fibonacci calculation appears off

Question

I currently have the following codes for my fibonacci calculations. I'm trying to calculate large numbers, but it appears once it gets to 100, the calculations are off. For fib(100), my code returns 3736710778780434371, but when I look at other sources, it tells me the correct calculation should be 354224848179261915075. Is there a problem in my code or does it have to do with my computer hardware or something else?

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

You're hitting an integer overflow! You can only calculate using a uint up to the size of a uint; once you go beyond its bounds, it will (silently) wrap back round again.

In your case, it looks as though a uint is 64 bits long. (Its size depends on the platform you're running on.) That means that you will be able to store values up to 2⁶⁴-1. If you then add one more, it'll wrap back to 0, and won't return an error.

If you convert the answer you're getting, and the right answer, into hex, then you'll see that this is the case. You're ending up with

  33DB76A7C594BFC3

whereas the right answer is

1333DB76A7C594BFC3

Note that your answer is correct as far as it goes... it just doesn't go far enough. You've only got the lower 64 bits of the answer; you're missing the other 13*2⁶⁴.

To correct it, you'll need to use an arbitrary size integer from Package big, instead of a uint.