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?
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.
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
}