CODEWITHSUNDEEP
gofloating-pointtype-conversioninteger
chidieberejoel
chidieberejoel

Reputation: 271

How to use Math.Pow with integers in Go

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
}

Upvotes: 23

Views: 46620

Answers (5)

Chris Concannon
Chris Concannon

Reputation: 443

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
    }

    if m == 1 {
        return n
    }

    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.

Upvotes: 17

Ganesan Rajagopal
Ganesan Rajagopal

Reputation: 51

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.

Upvotes: 5

Eissa N.
Eissa N.

Reputation: 1725

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
}

Upvotes: 11

Alan Donovan
Alan Donovan

Reputation: 11

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.

Upvotes: 1

nikoksr
nikoksr

Reputation: 440

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.

Upvotes: 24

Related Questions