我不断收到错误:
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
}
func powInt(x, y int) int {
return int(math.Pow(float64(x), float64(y)))
}
以防您必须重复使用它并保持更干净。
如果您的输入是
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
}
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)))
}
结果:
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 倍以上。
由于没有人提到对整数
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
}
虽然 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
}
在我的基准测试中,这几乎是递归版本的两倍。
如果您想要整数的精确幂,请使用 (*big.Int).Exp。当幂大于 2 时,你可能会很快溢出 int64。