在Golang中计算大指数幂。

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

Calculating large exponentiation in Golang

问题

我一直在尝试在Golang中计算2^100。我了解到了数字类型的限制，并尝试使用math/big包。以下是我尝试过的代码，但我无法弄清楚为什么它不起作用。

我使用了二的幂次计算的方法来计算指数。

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	two := big.NewInt(2)
  10. 	hundred := big.NewInt(50)
  11. 	fmt.Printf("2 ** 100 is %d\n", ExpByPowOfTwo(two, hundred))
  12. }
  14. func ExpByPowOfTwo(base, power *big.Int) *big.Int {
  15. 	result := big.NewInt(1)
  16. 	zero := big.NewInt(0)
  17. 	for power != zero {
  18. 		if modBy2(power) != zero {
  19. 			multiply(result, base)
  20. 		}
  21. 		power = divideBy2(power)
  22. 		base = multiply(base, base)
  23. 	}
  24. 	return result
  25. }
  27. func modBy2(x *big.Int) *big.Int {
  28. 	return big.NewInt(0).Mod(x, big.NewInt(2))
  29. }
  31. func divideBy2(x *big.Int) *big.Int {
  32. 	return big.NewInt(0).Div(x, big.NewInt(2))
  33. }
  35. func multiply(x, y *big.Int) *big.Int {
  36. 	return big.NewInt(0).Mul(x, y)
  37. }
英文:

I've been trying to calculating 2^100 in Golang. I understand the limit of numeric type and tried using math/big package. Here's what I've tried but I can't figure out why it doesn't work.

I've used computation by powers of two method to calculate the exponentiation.

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	two := big.NewInt(2)
  10. 	hundred := big.NewInt(50)
  11. 	fmt.Printf("2 ** 100	is %d\n", ExpByPowOfTwo(two, hundred))
  12. }
  14. func ExpByPowOfTwo(base, power *big.Int) *big.Int {
  15. 	result := big.NewInt(1)
  16. 	zero := big.NewInt(0)
  17. 	for power != zero {
  18. 		if modBy2(power) != zero {
  19. 			multiply(result, base)
  20. 		}
  21. 		power = divideBy2(power)
  22. 		base = multiply(base, base)
  23. 	}
  24. 	return result
  25. }
  27. func modBy2(x *big.Int) *big.Int {
  28. 	return big.NewInt(0).Mod(x, big.NewInt(2))
  29. }
  31. func divideBy2(x *big.Int) *big.Int {
  32. 	return big.NewInt(0).Div(x, big.NewInt(2))
  33. }
  35. func multiply(x, y *big.Int) *big.Int {
  36. 	return big.NewInt(0).Mul(x, y)
  37. }

答案1

得分: 19

BigInt包允许您以对数时间计算x^y（由于某种原因它被称为exp）。您只需要将nil作为最后一个参数传递即可。

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	fmt.Println(new(big.Int).Exp(big.NewInt(5), big.NewInt(20), nil))
  10. }

如果您想自己计算它，请看一下我的实现：

  1. func powBig(a, n int) *big.Int{
  2.     tmp := big.NewInt(int64(a))
  3.     res := big.NewInt(1)
  4.     for n > 0 {
  5.         temp := new(big.Int)
  6.         if n % 2 == 1 {
  7.             temp.Mul(res, tmp)
  8.             res = temp
  9.         }
  10.         temp = new(big.Int)
  11.         temp.Mul(tmp, tmp)
  12.         tmp = temp
  13.         n /= 2
  14.     }
  15.     return res
  16. }

或者在Go Playground上尝试一下。

英文:

BigInt package allows you to calculate x^y in log time (for some reason it is called exp). All you need is to pass nil as a last parameter.

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	fmt.Println(new(big.Int).Exp(big.NewInt(5), big.NewInt(20), nil))
  10. }

If you are interested how to calculate it by yourself, take a look at my implementation:

  1. func powBig(a, n int) *big.Int{
  2.     tmp := big.NewInt(int64(a))
  3.     res := big.NewInt(1)
  4.     for n > 0 {
  5.         temp := new(big.Int)
  6.         if n % 2 == 1 {
  7.             temp.Mul(res, tmp)
  8.             res = temp
  9.         }
  10.         temp = new(big.Int)
  11.         temp.Mul(tmp, tmp)
  12.         tmp = temp
  13.         n /= 2
  14.     }
  15.     return res
  16. }

or play with it on go playground.

答案2

得分: 13

例如，

  1. package main
  3. import (
  4.     "fmt"
  5.     "math/big"
  6. )
  8. func main() {
  9.     z := new(big.Int).Exp(big.NewInt(2), big.NewInt(100), nil)
  10.     fmt.Println(z)
  11. }

输出：

  1. 1267650600228229401496703205376

由于它是2的幂，你也可以进行位移操作：

  1. package main
  3. import (
  4.     "fmt"
  5.     "math/big"
  6. )
  8. func main() {
  9.     z := new(big.Int).Lsh(big.NewInt(1), 100)
  10.     fmt.Println(z)
  11. }

输出：

  1. 1267650600228229401496703205376
英文:

For example,

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	z := new(big.Int).Exp(big.NewInt(2), big.NewInt(100), nil)
  10. 	fmt.Println(z)
  11. }

Output:

  1. 1267650600228229401496703205376

Since it's a power of two, you could also do a bit shift:

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	z := new(big.Int).Lsh(big.NewInt(1), 100)
  10. 	fmt.Println(z)
  11. }

Output:

  1. 1267650600228229401496703205376

答案3

得分: 2

如果 power % 2 == 0，你立即返回。相反，你只想得到 base ** (power / 2) 的 result。然后将 result * result 相乘，如果 power 是偶数，则将 base 乘以该结果。

英文:

You are returning immediately if power % 2 == 0. Instead, you just want to get the result of base ** (power /2). Then multiply result * result, and if power is even then multiply base to that.

答案4

得分: 2

计算2的100次方

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	n := big.NewInt(0)
  10. 	fmt.Println(n.SetBit(n, 100, 1))
  11. }

Playground

英文:

To compute 2^100

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  9. 	n := big.NewInt(0)
  10. 	fmt.Println(n.SetBit(n, 100, 1))
  11. }

Playground

答案5

得分: 1

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  10. 	bigx, power10 := new(big.Int), new(big.Int)
  11. 	var x int64
  12. 	bigx.SetInt64(x)                          //将int64类型的x设置给bigx
  13. 	power10.Exp(big.NewInt(10), bigx, nil)     //power10 *big.Int指向解决方案
  15. 	str10 := power10.Text(10)
  16. 	fmt.Printf(str10)                          //打印出数字并自行检查
  18. }
  1. package main
  3. import (
  4. 	"fmt"
  5. 	"math/big"
  6. )
  8. func main() {
  10. 	bigx, power10 := new(big.Int), new(big.Int)
  11. 	var x int64
  12. 	bigx.SetInt64(x)                          //将int64类型的x设置给bigx
  13. 	power10.Exp(big.NewInt(10), bigx, nil)     //power10 *big.Int指向解决方案
  15. 	str10 := power10.Text(10)
  16. 	fmt.Printf(str10)                          //打印出数字并自行检查
  18. }
英文: 
  1. package main
  3. import(
  4.     "fmt"
  5.     "math/big"
  6. )
  8. func main() {
  10.     bigx, power10 := new(big.Int), new(big.Int)
  11.     var x int64
  12.     bigx.SetInt64(x) //set x int64 to bigx
  13.     power10.Exp(big.NewInt(10), bigx, nil) //power10 *big.Int points to solution
  15.     str10 := power10.Text(10)
  16.     fmt.Printf(str10) // print out the number and check for your self
  18. }

huangapple
  • 本文由 发表于 2015年5月12日 13:00:12
  • 转载请务必保留本文链接：https://go.coder-hub.com/30182129.html
  • exponentiation
  • go
匿名

发表评论

匿名网友

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

确定