Comment convertir un int en bigint dans golang?

Je suis en train de mettre en œuvre rapide double de fibonacci de l'algorithme tel que décrit ici:

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

Cela fonctionne très bien pour des petits nombres; toutefois, lorsque le nombre d'entrée sont de plus en plus, le programme renvoie un résultat erroné. J'ai donc essayé d'utiliser bigInt de 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))
}

Cependant, d'aller construire se plaint que

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

La façon d'atténuer ce problème?

  • Essayez de gros.Int64(int nombre)
InformationsquelleAutor Nick | 2015-11-12
  1. 6

    Utilisation big.NewInt() au lieu de big.Int(). big.Int() est juste la conversion de type.
    Vous devez vérifier la documentation de big le paquet

    Vous devriez surtout utiliser les méthodes de la forme func (z *T) Binary(x, y *T) *T //z = x op y

    Pour multiplier 2 arguments, vous devez fournir variable résultat, après appel Mul méthode. Ainsi, par exemple, pour obtenir le résultat de la 2*2 vous avez besoin de:

    big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))

    Vous pouvez essayer d'exemple de travail sur la Aller de l'aire de jeux

    Aussi, vous pouvez créer l'extension des fonctions comme:

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

    Afin de rendre le code plus lisible:

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

    L'essayer sur le Aller de l'aire de jeux

    • J'ai eu cannot use big.NewInt(0) (type *big.Int) as type big.Int in return argument
    • Parce que big.NewInt retourne le pointeur de *big.Int
    • Votre idée de la fonction d'extension est vraiment génial! Elle rend le code beaucoup plus propre! Merci beaucoup! P. S.: c := Mul(a, Sub(Mul(b, big.NewInt(2)), a)) ressemble LISP : )
    • "L'idée de l'extension de la fonction" n'est pas si brillante, si l'on se soucie d'allocations et de la performance. Pré-Go1.0 le math/grande bibliothèque fonctionnent de la même manière, mais il a été changé à sa forme actuelle, de sorte que (plus) efficace du code peut être écrit cela n'est pas le test de stress le garbage collector.
    InformationsquelleAutor RoninDev