英文:
How to convert int to bigint in golang?
问题
我正在尝试实现快速双倍斐波那契算法，如这里所描述的：
// 快速双倍斐波那契算法
package main
import "fmt"
// (公共) 返回 F(n)。
func fibonacci(n int) int {
if n < 0 {
panic("未实现负数参数")
}
fst, _ := fib(n)
return fst
}
// (私有) 返回元组 (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))
}
这对于小数值的输入效果很好；然而，当输入的数值变大时，程序返回错误的结果。因此，我尝试使用 math/big 包中的 big.Int：
// 快速双倍斐波那契算法
package main
import (
"fmt"
"math/big"
)
// (公共) 返回 F(n)。
func fibonacci(n int) big.Int {
if n < 0 {
panic("未实现负数参数")
}
fst, _ := fib(n)
return fst
}
// (私有) 返回元组 (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 := *big.NewInt(0).Mul(&a, big.NewInt(2)).Sub(big.NewInt(0).Mul(&b, &b), &a)
d := *big.NewInt(0).Add(big.NewInt(0).Mul(&a, &a), big.NewInt(0).Mul(&b, &b))
if n%2 == 0 {
return c, d
} else {
return d, *big.NewInt(0).Add(&c, &d)
}
}
func main() {
fmt.Println(fibonacci(123))
fmt.Println(fibonacci(124))
}
然而，go build 报错：
无法将 0 (类型 int) 转换为 big.Int 类型
如何解决这个问题？
英文:
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?
答案1
得分: 17
使用big.NewInt()代替big.Int()。big.Int()只是类型转换。
你需要查看big包的文档。
你应该主要使用形式为func (z *T) Binary(x, y *T) *T // z = x op y的方法。
要乘以两个参数，你需要提供结果变量，然后调用Mul方法。例如，要得到2*2的结果，你需要：
big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))
你可以在<kbd>Go playground</kbd>上尝试工作示例。
你还可以创建扩展函数，例如：
func Mul(x, y *big.Int) *big.Int {
return big.NewInt(0).Mul(x, y)
}
以使代码更易读：
// 快速倍增斐波那契算法
package main
import (
"fmt"
"math/big"
)
// （公共）返回F(n)。
func fibonacci(n int) *big.Int {
if n < 0 {
panic("未实现负数参数")
}
fst, _ := fib(n)
return fst
}
// （私有）返回元组（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)
}
在<kbd>Go playground</kbd>上试一试。
英文:
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 <kbd>Go playground</kbd>
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 <kbd>Go playground</kbd>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论