英文:
Is there a pow method in bigInt package in Go
问题
我正在查看Go语言的大整数算术文档，并尝试找到一个适用于计算a^n（类似于Python中的pow(a, n)）的方法。
令我惊讶的是，在一些直接的函数（如GCD、Binomial）和不太直接的函数（如modinverse）中，我找不到pow函数。我是漏掉了还是需要自己编写呢？
英文:
I am looking at the documentation of a big integer arithmetic in Go and trying to find a method suitable for calculation of a^n (something like pow(a, n) in python).
To my surprise among some straightforward functions like GCD, Binomial and not really straightforward as modinverse I can not find pow. Am I missing it or should I write my own?
答案1
得分: 3
func (z *Int) Exp(x, y, m *Int) *Int
> Exp 将 z 设置为 x^y mod |m|（即忽略 m 的符号），并返回 z。如果 y <= 0，则结果为 1 mod |m|；如果 m == nil 或 m == 0，则 z = x^y。参见 Knuth 的第 2 卷第 4.6.3 节。
英文:
func (z *Int) Exp(x, y, m *Int) *Int
> Exp sets z = x^y mod |m| (i.e. the sign of m is ignored), and returns z. If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x^y. See Knuth, volume 2, section 4.6.3.
答案2
得分: 1
因为我几乎完成了自己的实现（Daniel的建议不起作用，因为你总是必须在那里提供一个模数），所以我在这里添加它，以防有人想看看它如何被高效地实现。这是Go Playground和我的函数：
func powBig(a, n int) *big.Int{
tmp := big.NewInt(int64(a))
res := big.NewInt(1)
for n > 0 {
temp := new(big.Int)
if n % 2 == 1 {
temp.Mul(res, tmp)
res = temp
}
temp = new(big.Int)
temp.Mul(tmp, tmp)
tmp = temp
n /= 2
}
return res
}
英文:
Because I almost finished my own implementation (Daniel's recommendation does not work, because you always have to provide a modulo there) I am adding it here in case someone would like to see how it might be implemented efficiently. Here is Go Playground and my function:
func powBig(a, n int) *big.Int{
tmp := big.NewInt(int64(a))
res := big.NewInt(1)
for n > 0 {
temp := new(big.Int)
if n % 2 == 1 {
temp.Mul(res, tmp)
res = temp
}
temp = new(big.Int)
temp.Mul(tmp, tmp)
tmp = temp
n /= 2
}
return res
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论