今天讲个有趣的算法：如何快速求 nmnm，其中 n 和 m 都是整数，今天小编就来聊一聊关于数据的收集与平均数的计算?接下来我们就一起去研究一下吧!
数据的收集与平均数的计算
今天讲个有趣的算法：如何快速求 nmnm，其中 n 和 m 都是整数。
为方便起见，此处假设 m >= 0，对于 m < 0 的情况，求出 n|m|n|m| 后再取倒数即可。
另外此处暂不考虑结果越界的情况（超过 int64 范围）。
当然不能用编程语言的内置函数，我们只能用加减乘除来实现。
n 的 m 次方的数学含义是：m 个 n 相乘：n*n*n...*n，也就是说最简单的方式是执行 m 次乘法。
直接用乘法实现的问题是性能不高，其时间复杂度是 O(m)，比如 329329 要执行 29 次乘法，而乘法运算是相对比较重的，我们看看能否采用什么方法将时间复杂度降低。
设 m = x y z（x、y、z 都是整数），我们知道有如下数学等式： nmnm = nx y znx y z = nx∗ny∗nznx∗ny∗nz。
也就是说，如果我们已经知道 nxnx、nyny、nznz 的值，是不是就可以直接用他们相乘得出 nmnm的结果？这样的话乘的次数就大大降低了。
于是问题就变成应该将 m 拆成怎样的几个数的和。
因为计算机是玩二进制的，我们尝试着将这些数跟 2 扯上联系（以 2 为底），看看会不会有奇迹发生。
我们看看具体的例子：329329。
我们将 29 做这样的拆分：29 = 16 8 4 1。
这个拆分有什么特点呢？右边的数都是 2 的 X 次方（24 23 22 2024 23 22 20）。
我们把上面的拆分带进公式：329=316∗38∗34∗31329=316∗38∗34∗31。
那我们能不能知道 316316、3838、3434、3131 是什么呢？
我们不用计算就知道 3131 是什么——但仅此而已。
不过我们可以用 3131 自乘 4 次的到 3434；然后再用 3434 自乘得到 3838；再通过 3838 自乘得到 316316。
好像有点感觉了——我们每做一次乘法，就能将结果翻倍（如 3434 自乘就变成 34∗34=3834∗34=38）。
如此，虽然也要多次乘法，但乘的次数从 29 次降到 9 次！
然后我们再回头看看上面的拆分：
29 = 16 8 4 1 = 24 23 22 2024 23 22 20 = 1∗24 1∗23 1∗22 0∗21 1∗201∗24 1∗23 1∗22 0∗21 1∗20 。
这不就是学校学的二进制转十进制吗（29 的二进制是 11101）？
329=316∗38∗34∗31329=316∗38∗34∗31 是说：取 29 的二进制表示中所有值是 1 的位，算出它们的指数值并相乘就得到最终的值。
我们用 go 语言实现一下：
// 求 a 的 n 次方 // a、n 是非负整数 func Pow(a,n int64) int64 { // 0 的任何次方都是 0 if a == 0 { return 0 } // 任何数的 0 次方都是 1 if n == 0 { return 1 } // 1 次方是它自身 if n == 1 { return a } // 用滚雪球的方式计算幂 // 雪球初始值是 1 var result int64 = 1 // 滚动因子初始化为 a 的 1 次方（a 自身） factor := a // 循环处理直到 n 变成 0（所有的二进制位都处理完了） for n != 0 { // 跟 1 做与运算，判断当前要处理的位是不是 1 // 之所以是直接跟 1 做与运算，因为后面每处理一轮都将 n 右移了一位，保证每次要处理的位都在最低位 if n & 1 != 0 { // 当前位是 1，需要乘进去 result *= factor } // 每轮结束时将滚动因子自乘 // 因为每行进一轮，指数都翻倍，整体结果就是自乘 // 比如本轮因子是 2**4，下一轮就是 2**8 // 2**8 = 2**(4 4) = 2**4 * 2**4 // （** 表示指数） factor *= factor // n 右移一位，将下一轮要处理的位放在最低位 n = n >> 1 } return result }有什么用呢？
很多语言内置的 pow 函数都只接受浮点数，浮点数的运算是非常重的，如果我们的程序需要频繁计算整数的幂，就可以采用 quick pow 算法代替语言内置的幂函数以提升性能。
我们对 go 语言内置的 math.Pow 和 quick pow 算法做个性能测试对比一下。
// 测试 3 的 29 次方的性能测试 var benchPowB int64 = 3 var benchPowP int64 = 29 // 上面的 quick pow 算法 func BenchmarkQuickPow(b *testing.B) { for i := 0; i < b.N; i { algo.Pow(benchPowB, benchPowP) } } // go 语言 math 包的 Pow 方法，只接受 float64 类型 func BenchmarkInnerPow(b *testing.B) { x := float64(benchPowB) y := float64(benchPowP) for i := 0; i < b.N; i { math.Pow(x, y) } } // 用简单乘法实现（3 自乘 29 次） func BenchmarkSimpleMulti(b *testing.B) { for i := 0; i < b.N; i { var r int64 = 1 var j int64 = 0 for ; j < benchPowP; j { r *= benchPowB } } }测试结果：
goos: darwin goarch: amd64 cpu: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz BenchmarkQuickPow-8 357897716 3.373 ns/op BenchmarkInnerPow-8 39162492 29.30 ns/op BenchmarkSimpleMulti-8 121066731 9.549 ns/op PASS ok command-line-arguments 4.894s从性能测试结果看，quick pow 算法比简单乘法快了好几倍，比 math.pow 快了近 10 倍。
所以，如果程序只需要求整数幂，而且能确保计算结果不会越界时，可以考虑使用 quick pow 算法代替语言内置的浮点函数。
文章来自https://www.cnblogs.com/linvanda/p/16425351.html
,
