How to use Math.Pow with integers in Golang

Question

I keep getting the error "cannot use a (type int) as type float64 in argument to math.Pow, cannot use x (type int) as type float64 in argument to math.Pow, invalid operation: math.Pow(a, x) % n (mismatched types float64 and int)"

func pPrime(n int) bool {
    var nm1 int = n - 1
    var x int = nm1/2
    a := 1;
    for  a < n {
        if  (math.Pow(a, x)) % n == nm1 {
            return true
        }
    }
    return false
}

Answer 1

func powInt(x, y int) int {
    return int(math.Pow(float64(x), float64(y)))
}

In case you have to reuse it and keep it a little more clean.

Answer 2

If your inputs are int and the output is always expected to be int, then you're dealing with 32-bit numbers. It's more efficient to write your own function to handle this multiplication rather than using math.Pow. math.Pow, as mentioned in the other answers, expects 64-bit values.

Here's a Benchmark comparison for 15^15 (which approaches the upper limits for 32-bit representation):

// IntPow calculates n to the mth power. Since the result is an int, it is assumed that m is a positive power
func IntPow(n, m int) int {
    if m == 0 {
        return 1
    }
    result := n
    for i := 2; i <= m; i++ {
        result *= n
    }
    return result
}

// MathPow calculates n to the mth power with the math.Pow() function
func MathPow(n, m int) int {
    return int(math.Pow(float64(n), float64(m)))
}

The result:

go test -cpu=1 -bench=.
goos: darwin
goarch: amd64
pkg: pow
BenchmarkIntPow15   195415786            6.06 ns/op
BenchmarkMathPow15  40776524            27.8 ns/op

I believe the best solution is that you should write your own function similar to IntPow(m, n int) shown above. My benchmarks show that it runs more than 4x faster on a single CPU core compared to using math.Pow.

Answer 3

Since nobody mentioned an efficient way (logarithmic) to do Pow(x, n) for integers x and n is as follows if you want to implement it yourself:

// Assumption: n >= 0
func PowInts(x, n int) int {
   if n == 0 { return 1 }
   if n == 1 { return x }
   y := PowInts(x, n/2)
   if n % 2 == 0 { return y*y }
   return x*y*y
}

Answer 4

If you want the exact exponentiation of integers, use (*big.Int).Exp. You're likely to overflow int64 pretty quickly with powers larger than two.