如何在 Golang 中将 Math.Pow 与整数一起使用

Question

我不断收到错误：

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)))
}

以防万一您必须重复使用它并保持更干净。

Answer 2

如果您的输入是

int

并且输出始终预计是

int

，那么您正在处理 32 位数字。编写自己的函数来处理此乘法比使用

math.Pow

更有效。

math.Pow

，正如其他答案中提到的，需要 64 位值。

这是 15^15 的基准比较（接近 32 位表示的上限）：

// 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)))
}

结果：

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

我相信最好的解决方案是您应该编写自己的函数，类似于上面所示的

IntPow(m, n int)

。我的基准测试显示，与使用

math.Pow

相比，它在单个 CPU 核心上的运行速度快了 4 倍以上。

Answer 3

由于没有人提到对整数

Pow(x, n)

和

x

进行

n

的有效方法（对数），如果您想自己实现，则如下所示：

// 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

虽然 Eissa 对于有效解决方案的上述回答在技术上是正确的，但递归可能会降低性能。请参阅实现基于整数的幂函数 pow(int, int) 的最有效方法以获得更优化的解决方案。这是翻译为 Go 的 C 解决方案：

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
}

在我的基准测试中，这几乎是递归版本的两倍。

Answer 5

如果您想要整数的精确幂，请使用 (*big.Int).Exp。当幂大于 2 时，你可能会很快溢出 int64。