Jak przekonwertować int na bigint w golangu?

Question

Próbuję zaimplementować szybki algorytm podwójne Fibonacciego jak opisano 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)) 
} 

Działa to dobrze dla małych ilościach; jednak, gdy numer wejścia staje się większy, program zwraca nieprawidłowy wynik. Więc starałem się używać bigInt z math/big opakowaniu:

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

jednak pójść budować zarzuca

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

Jak złagodzić ten problem?

Answer 1

Użyj big.NewInt() zamiast big.Int(). big.Int() jest po prostu odlewaniem typu. Trzeba sprawdzić documentation of big package
Należy przede wszystkim stosować metody z formą func (z *T) Binary(x, y *T) *T // z = x op y
pomnożyć 2 argumenty musisz dostarczyć zmienną wynikową, po to nazwać Mul metody. Tak więc, na przykład, aby uzyskać wynik 2 * 2 należy:
big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))

Można spróbować przykład pracuje nad Go playground

Ponadto można tworzyć funkcje rozszerzeń, takich jak:

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

Aby kod był bardziej czytelny:

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

Spróbuj na Go playground