How to convert int to bigint in golang?

Question

I am trying to implement a fast double fibonacci algorithm as described here :

// Fast doubling Fibonacci algorithm package main import "fmt" // (Public) Returns F(n). func fibonacci(n int) int { if n < 0 { panic("Negative arguments not implemented") } fst, _ := fib(n) return fst } // (Private) Returns the tuple (F(n), F(n+1)). func fib(n int) (int, int) { if n == 0 { return 0, 1 } a, b := fib(n / 2) c := a * (b*2 - a) d := a*a + b*b if n%2 == 0 { return c, d } else { return d, c + d } } func main() { fmt.Println(fibonacci(13)) fmt.Println(fibonacci(14)) } 

This works great for small numbers; however, when the input number increases, the program returns an incorrect result. So I tried using the bigInt package from math/big :

 // Fast doubling Fibonacci algorithm package main import ( "fmt" "math/big" ) // (Public) Returns F(n). func fibonacci(n int) big.Int { if n < 0 { panic("Negative arguments not implemented") } fst, _ := fib(n) return fst } // (Private) Returns the tuple (F(n), F(n+1)). func fib(n int) (big.Int, big.Int) { if n == 0 { return big.Int(0), big.Int(1) } a, b := fib(n / 2) c := a * (b*2 - a) d := a*a + b*b if n%2 == 0 { return c, d } else { return d, c + d } } func main() { fmt.Println(fibonacci(123)) fmt.Println(fibonacci(124)) } 

However, go build complains that

 cannot convert 0 (type int) to type big.Int 

How to reduce this problem?

Answer 1

Use big.NewInt() instead of big.Int() . big.Int() is just casting. You need to check the package documentation for big
Basically you should use methods with the form func (z *T) Binary(x, y *T) *T // z = x op y
To multiply 2 arguments, you need to provide a result variable after calling the Mul method. So, for example, to get the result 2 * 2, you need:
big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))

You can try the working example on Go to the site

You can also create extension functions, such as:

 func Mul(x, y *big.Int) *big.Int { return big.NewInt(0).Mul(x, y) } 

To make the code more readable:

 // Fast doubling Fibonacci algorithm package main import ( "fmt" "math/big" ) // (Public) Returns F(n). func fibonacci(n int) *big.Int { if n < 0 { panic("Negative arguments not implemented") } fst, _ := fib(n) return fst } // (Private) Returns the tuple (F(n), F(n+1)). func fib(n int) (*big.Int, *big.Int) { if n == 0 { return big.NewInt(0), big.NewInt(1) } a, b := fib(n / 2) c := Mul(a, Sub(Mul(b, big.NewInt(2)), a)) d := Add(Mul(a, a), Mul(b, b)) if n%2 == 0 { return c, d } else { return d, Add(c, d) } } func main() { fmt.Println(fibonacci(123)) fmt.Println(fibonacci(124)) } func Mul(x, y *big.Int) *big.Int { return big.NewInt(0).Mul(x, y) } func Sub(x, y *big.Int) *big.Int { return big.NewInt(0).Sub(x, y) } func Add(x, y *big.Int) *big.Int { return big.NewInt(0).Add(x, y) } 

Try on Go to the site