How to convert int to bigint in golang?

Question

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?

Try big.Int64(int-number)

aggaton
– aggaton

2015-11-12 03:48:54 +00:00
Commented Nov 12, 2015 at 3:48 — aggaton
– aggaton, Commented Nov 12, 2015 at 3:48

RoninDev · Accepted Answer · 2015-11-12 06:01:30Z

17

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

edited Nov 12, 2015 at 6:01

answered Nov 12, 2015 at 3:49

RoninDev

5,7263 gold badges25 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Nick Over a year ago

I got cannot use big.NewInt(0) (type *big.Int) as type big.Int in return argument

Nick Over a year ago

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 : )

Dave C Over a year ago

@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.

Collectives™ on Stack Overflow

How to convert int to bigint in golang?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related