Come convertire int in bigint in golang?

Question

Sto cercando di implementare velocemente algoritmo doppia Fibonacci come descritto 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)) 
} 

Questo funziona bene per i piccoli numeri; tuttavia, quando il numero di input aumenta, il programma restituisce un risultato errato. Così ho cercato di usare bigInt da math/big pacchetto:

// 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)) 
} 

Tuttavia, va accumulo lamenta che

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

Come per mitigare questo problema?

Answer 1

Utilizzare big.NewInt() anziché big.Int(). big.Int() è solo digitare casting. È necessario controllare documentation of big package
Si dovrebbe per lo più usare metodi con modulo func (z *T) Binary(x, y *T) *T // z = x op y
Per moltiplicare 2 argomenti è necessario fornire variabile di risultato, dopo che è chiamata Mul metodo. Così, ad esempio, per ottenere il risultato di 2 * 2 è necessario:
big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))

si può provare ad esempio a lavorare sul Go playground

Inoltre è possibile creare funzioni di estensione come:

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

per rendere il codice più leggibile:

// 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) 
} 

Prova sul Go playground