use math/big to compute fibo with memoization

big_fibo.go

package main

import "fmt"
import "math/big"

// we can't use a reference type as a key (*big.Int) so we need to cast to string to keep track
var seen = make(map[string]*big.Int)

func fibo(n *big.Int) *big.Int {
	zero := big.NewInt(0)
	one := big.NewInt(1)
	two := big.NewInt(2)
	seen[zero.String()] = zero
	seen[one.String()] = one
	if val, ok := seen[n.String()]; ok {
		return val
	} else {
		x := big.NewInt(0)
		y := big.NewInt(0)
		res := big.NewInt(0)
		x.Sub(n, one)
		y.Sub(n, two)
		res.Add(fibo(x), fibo(y))
		seen[n.String()] = res
		return res
	}

}

func main() {
	for i := 0; i < 1000; i++ {
		n := big.NewInt(int64(i))
		fmt.Println(n, fibo(n))
	}
}