How to convert int to bigint in golang?

huangapple
go评论120阅读模式
英文:

How to convert int to bigint in golang?

问题

我正在尝试实现快速双倍斐波那契算法，如这里所描述的：

  1. // 快速双倍斐波那契算法
  2. package main
  4. import "fmt"
  6. // (公共) 返回 F(n)。
  7. func fibonacci(n int) int {
  8.     if n < 0 {
  9.         panic("未实现负数参数")
  10.     }
  11.     fst, _ := fib(n)
  12.     return fst
  13. }
  15. // (私有) 返回元组 (F(n), F(n+1))。
  16. func fib(n int) (int, int) {
  17.     if n == 0 {
  18.         return 0, 1
  19.     }
  20.     a, b := fib(n/2)
  21.     c := a * (b*2 - a)
  22.     d := a*a + b*b
  23.     if n%2 == 0 {
  24.         return c, d
  25.     } else {
  26.         return d, c + d
  27.     }
  28. }
  30. func main() {
  31.     fmt.Println(fibonacci(13))
  32.     fmt.Println(fibonacci(14))
  33. }

这对于小数值的输入效果很好；然而，当输入的数值变大时，程序返回错误的结果。因此，我尝试使用 math/big 包中的 big.Int：

  1. // 快速双倍斐波那契算法
  2. package main
  4. import (
  5.     "fmt"
  6.     "math/big"
  7. )
  9. // (公共) 返回 F(n)。
  10. func fibonacci(n int) big.Int {
  11.     if n < 0 {
  12.         panic("未实现负数参数")
  13.     }
  14.     fst, _ := fib(n)
  15.     return fst
  16. }
  18. // (私有) 返回元组 (F(n), F(n+1))。
  19. func fib(n int) (big.Int, big.Int) {
  20.     if n == 0 {
  21.         return *big.NewInt(0), *big.NewInt(1)
  22.     }
  23.     a, b := fib(n/2)
  24.     c := *big.NewInt(0).Mul(&a, big.NewInt(2)).Sub(big.NewInt(0).Mul(&b, &b), &a)
  25.     d := *big.NewInt(0).Add(big.NewInt(0).Mul(&a, &a), big.NewInt(0).Mul(&b, &b))
  26.     if n%2 == 0 {
  27.         return c, d
  28.     } else {
  29.         return d, *big.NewInt(0).Add(&c, &d)
  30.     }
  31. }
  33. func main() {
  34.     fmt.Println(fibonacci(123))
  35.     fmt.Println(fibonacci(124))
  36. }

然而，go build 报错：

  1. 无法将 0 (类型 int) 转换为 big.Int 类型

如何解决这个问题？

英文:

I'm trying to implement fast double Fibonacci algorithm as described here:

  1. // Fast doubling Fibonacci algorithm
  2. package main
  4. import &quot;fmt&quot;
  6. //  (Public) Returns F(n).
  7. func fibonacci(n int) int {
  8. 	if n &lt; 0 {
  9. 		panic(&quot;Negative arguments not implemented&quot;)
  10. 	}
  11. 	fst, _ := fib(n)
  12. 	return fst
  13. }
  15. // (Private) Returns the tuple (F(n), F(n+1)).
  16. func fib(n int) (int, int) {
  17. 	if n == 0 {
  18. 		return 0, 1
  19. 	}
  20. 	a, b := fib(n / 2)
  21. 	c := a * (b*2 - a)
  22. 	d := a*a + b*b
  23. 	if n%2 == 0 {
  24. 		return c, d
  25. 	} else {
  26. 		return d, c + d
  27. 	}
  28. }
  30. func main() {
  31. 	fmt.Println(fibonacci(13))
  32. 	fmt.Println(fibonacci(14))
  33. }

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:

  1. // Fast doubling Fibonacci algorithm
  2. package main
  4. import (
  5. 	&quot;fmt&quot;
  6. 	&quot;math/big&quot;
  7. )
  9. //  (Public) Returns F(n).
  10. func fibonacci(n int) big.Int {
  11. 	if n &lt; 0 {
  12. 		panic(&quot;Negative arguments not implemented&quot;)
  13. 	}
  14. 	fst, _ := fib(n)
  15. 	return fst
  16. }
  18. // (Private) Returns the tuple (F(n), F(n+1)).
  19. func fib(n int) (big.Int, big.Int) {
  20. 	if n == 0 {
  21. 		return big.Int(0), big.Int(1)
  22. 	}
  23. 	a, b := fib(n / 2)
  24. 	c := a * (b*2 - a)
  25. 	d := a*a + b*b
  26. 	if n%2 == 0 {
  27. 		return c, d
  28. 	} else {
  29. 		return d, c + d
  30. 	}
  31. }
  33. func main() {
  34. 	fmt.Println(fibonacci(123))
  35. 	fmt.Println(fibonacci(124))
  36. }

However, go build complains that

  1. 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>上尝试工作示例。

你还可以创建扩展函数，例如：

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

以使代码更易读：

  1. // 快速倍增斐波那契算法
  2. package main
  4. import (
  5.     "fmt"
  6.     "math/big"
  7. )
  9. // （公共）返回F(n)。
  10. func fibonacci(n int) *big.Int {
  11.     if n < 0 {
  12.         panic("未实现负数参数")
  13.     }
  14.     fst, _ := fib(n)
  15.     return fst
  16. }
  18. // （私有）返回元组（F(n)，F(n+1)）。
  19. func fib(n int) (*big.Int, *big.Int) {
  20.     if n == 0 {
  21.         return big.NewInt(0), big.NewInt(1)
  22.     }
  23.     a, b := fib(n / 2)
  24.     c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))
  25.     d := Add(Mul(a, a), Mul(b, b))
  26.     if n%2 == 0 {
  27.         return c, d
  28.     } else {
  29.         return d, Add(c, d)
  30.     }
  31. }
  33. func main() {
  34.     fmt.Println(fibonacci(123))
  35.     fmt.Println(fibonacci(124))
  36. }
  38. func Mul(x, y *big.Int) *big.Int {
  39.     return big.NewInt(0).Mul(x, y)
  40. }
  41. func Sub(x, y *big.Int) *big.Int {
  42.     return big.NewInt(0).Sub(x, y)
  43. }
  44. func Add(x, y *big.Int) *big.Int {
  45.     return big.NewInt(0).Add(x, y)
  46. }

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

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

To make code more readable:

  1. // Fast doubling Fibonacci algorithm
  2. package main
  4. import (
  5. 	&quot;fmt&quot;
  6. 	&quot;math/big&quot;
  7. )
  9. //  (Public) Returns F(n).
  10. func fibonacci(n int) *big.Int {
  11. 	if n &lt; 0 {
  12. 		panic(&quot;Negative arguments not implemented&quot;)
  13. 	}
  14. 	fst, _ := fib(n)
  15. 	return fst
  16. }
  18. // (Private) Returns the tuple (F(n), F(n+1)).
  19. func fib(n int) (*big.Int, *big.Int) {
  20. 	if n == 0 {
  21. 		return big.NewInt(0), big.NewInt(1)
  22. 	}
  23. 	a, b := fib(n / 2)
  24. 	c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))
  25. 	d := Add(Mul(a, a), Mul(b, b))
  26. 	if n%2 == 0 {
  27. 		return c, d
  28. 	} else {
  29. 		return d, Add(c, d)
  30. 	}
  31. }
  33. func main() {
  34. 	fmt.Println(fibonacci(123))
  35. 	fmt.Println(fibonacci(124))
  36. }
  38. func Mul(x, y *big.Int) *big.Int {
  39. 	return big.NewInt(0).Mul(x, y)
  40. }
  41. func Sub(x, y *big.Int) *big.Int {
  42. 	return big.NewInt(0).Sub(x, y)
  43. }
  44. func Add(x, y *big.Int) *big.Int {
  45. 	return big.NewInt(0).Add(x, y)
  46. }

Try it on the <kbd>Go playground</kbd>

huangapple
  • 本文由 发表于 2015年11月12日 11:37:50
  • 转载请务必保留本文链接：https://go.coder-hub.com/33664041.html
  • go
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定