Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Teams

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

I'm trying to implement 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 fine for small numbers; however, when the input number get larger, the program returns a wrong result. So I tried to use bigInt from math/big package:
// 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 mitigate this problem?
Use big.NewInt() instead of big.Int(). big.Int() is just type casting.
You need to check out documentation of big package

You should mostly use methods with form func (z *T) Binary(x, y *T) *T    // z = x op y

To multiply 2 arguments you need to provide result variable, after it call Mul method. So, for example, to get result of 2*2 you need to:

big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))
You can try working example on the Go playground
Also you can create extension functions like:
func Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
To make 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 it on the Go playground
                Your idea of extension function is really brilliant! It makes the code much cleaner! Thank you very much! P.S.:    c := Mul(a, Sub(Mul(b, big.NewInt(2)), a)) looks like LISP : )
– Nick
                Nov 12, 2015 at 8:38
                @Nick, The "idea of extension function" isn't so brilliant if one cares about allocations and performance. Pre-Go1.0 the math/big library operated similarly but it was changed to it's current form so that (more) efficient code could be written that didn't just stress test the garbage collector.
– Dave C
                Oct 29, 2017 at 16:24
        
Thanks for contributing an answer to Stack Overflow!
Please be sure to answer the question. Provide details and share your research!
But avoid …
Asking for help, clarification, or responding to other answers.
Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.