15

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
}
chidieberejoel
  • 191
  • 1
  • 1
  • 5
  • 4
    [Convert your ints to floats](https://tour.golang.org/basics/13) for use in a function that takes floats. – Adrian Sep 28 '20 at 20:08
  • 2
    Am I the only one surprised of seeing Go does not have an integer `math.Pow`? As a newbie, it makes me question whether to switch to other languages. – ibarrond Nov 30 '21 at 15:38

5 Answers5

15
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.

nikoksr
  • 342
  • 4
  • 10
  • 5
    while this keeps things cleaner, I think you'd be better to avoid using `math.Pow` entirely if you're going to write your own function that accepts `int` arguments and returns `int`. As I mention in my answer, using a loop to do the multiplication yourself results in performance improvements, plus you remove the external package dependency – Chris Concannon Mar 01 '21 at 21:05
11

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.

Chris Concannon
  • 383
  • 4
  • 9
  • How would you deal with pows to the power of a negative number? e.g: 2 ^ -1 – cesartalves Mar 02 '21 at 12:43
  • 1
    @cesartalves the expected result wouldn't be an integer, so casting the values as `float64` and using `math.Pow` would be appropriate if there are negative exponents involved – Chris Concannon Mar 02 '21 at 20:47
  • 1
    Makes sense. I would just improve on the answer by allowing the value of 0 to be passed to `m`, since `x ^ 0 = 1` :) – cesartalves Mar 02 '21 at 21:02
  • ah I see what you're saying. I'll elaborate on the `IntPow()` description to clarify constraints – Chris Concannon Mar 02 '21 at 22:06
  • 5
    It's terrible that Go would not include IntPow. Your implementation is linear in time complexity whereas decent standard library should provide trivial implementation with logarithmic complexity. – Cthulhu Mar 11 '21 at 08:35
9

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
}
Eissa N.
  • 1,695
  • 11
  • 18
2

While the above answer by Eissa for an efficient solution is technically correct, the recursion probably kills the performance. See The most efficient way to implement an integer based power function pow(int, int) for a more optimal solution. Here's the C solution translated to Go:

func IntPow(base, exp int) int {
    result := 1
    for {
        if exp & 1 == 1 {
            result *= base
        }
        exp >>= 1
        if exp == 0 {
            break
        }
        base *= base
    }

    return result
}

In my benchmarking this is nearly twice as fast as the recursive version.

Ganesan Rajagopal
  • 21
  • 2
  • Pedantic: The "C" solution would use `exp & 1 == 1` --> `exp % 2` and `exp >>= 1` to `exp /= 2` to correctly handle all 3 possible `int` encodings and let the compiler emit efficient code. Of course `exp < 0` remains a problem. – chux - Reinstate Monica Mar 11 '23 at 23:22
1

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.

ouflak
  • 2,458
  • 10
  • 44
  • 49
Alan Donovan
  • 11
  • 1