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))
}
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 264-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*264.
To correct it, you'll need to use an arbitrary size integer from Package big, instead of a uint.
Here is a version using big.Int which produces the correct answer (playground)
package main
import (
"fmt"
"math/big"
)
func fib(N uint) *big.Int {
var table []*big.Int
table = make([]*big.Int, N+1)
table[0] = new(big.Int).SetInt64(0)
table[1] = new(big.Int).SetInt64(1)
for i := uint(2); i <= N; i += 1 {
table[i] = new(big.Int).Add(table[i-1], table[i-2])
}
return table[N]
}
func main() {
fmt.Println(fib(100))
}
Which produces
354224848179261915075