小朋友学算法（1）：求幂pow函数的四种实现方式

小朋友学算法（1）：求幂pow函数的四种实现方式

​​更新时间：2020-5-4​​

一、非递归方法

#include double pow1(double x, unsigned int n){ int res = 1; while(n--) { res *= x; } return res;}int main(){ printf("2 ^ 10 = %f\n", pow1(2, 10)); printf("5 ^ 3 = %f\n", pow1(5, 3)); printf("10 ^ 0 = %f\n", pow1(10, 0)); return 0;}

运行结果：

2 ^ 10 = 1024.0000005 ^ 3 = 125.00000010 ^ 0 = 1.000000

二、递归方法1

#include double pow2(double x, unsigned int n){ if(0 == n) { return 1; } if(1 == n) { return x; } return x * pow2(x, n - 1);}int main(){ printf("2 ^ 10 = %f\n", pow2(2, 10)); printf("5 ^ 3 = %f\n", pow2(5, 3)); printf("10 ^ 0 = %f\n", pow2(10, 0)); return 0;}

三、快速幂位运算解法

上面三种方法都有一个缺点，就是循环次数多，效率不高。举个例子： 3 ^ 19 = 3 * 3 * 3 * … * 3 直接乘要做18次乘法。但事实上可以这样做，先求出3的2^k次幂： 3 ^ 2 = 3 * 3 3 ^ 4 = (3 ^ 2) * (3 ^ 2) 3 ^ 8 = (3 ^ 4) * (3 ^ 4) 3 ^ 16 = (3 ^ 8) * (3 ^ 8) 再相乘： 3 ^ 19 = 3 ^ (16 + 2 + 1) = (3 ^ 16) * (3 ^ 2) * 3 这样只要做7次乘法就可以得到结果。

如果幂更大的话，节省的乘法次数更多（但有可能放不下）。即使加上一些辅助的存储和运算，也比直接乘高效得多。

我们发现，把19转为2进制数：10011，其各位就是要乘的数。这提示我们利用求二进制位的算法，所以就可以写出下面的代码:

#include double pow3(double x, int n){ double res = 1; while (n) { if (n & 1) // 等价于 if (n % 2 != 0) { res *= x; } n >>= 1; x *= x; } return res;}int main(){ printf("2 ^ 10 = %f\n", pow3(2, 10)); printf("5 ^ 3 = %f\n", pow3(5, 3)); printf("10 ^ 0 = %f\n", pow3(10, 0)); printf("3 ^ 19 = %f\n", pow3(3, 19)); return 0;}

运行结果：

2 ^ 10 = 1024.0000005 ^ 3 = 125.00000010 ^ 0 = 1.0000003 ^ 19 = 1162261467.000000

四、快速幂递归解法

#include double pow4(double x, unsigned int n){ if(0 == n) { return 1; } if(1 == n) { return x; } double tmp = (n & 1) ? x : 1; return tmp * pow4(x * x, n / 2);}int main(){ printf("2 ^ 10 = %f\n", pow4(2, 10)); printf("5 ^ 3 = %f\n", pow4(5, 3)); printf("10 ^ 0 = %f\n", pow4(10, 0)); return 0;}

五、效率比较

#include #include #include using namespace std;#define COUNT 100000000double pow1(double x, unsigned int n){ int res = 1; while(n--) { res *= x; } return res;}double pow2(double x, unsigned int n){ if(0 == n) { return 1; } if(1 == n) { return x; } return x * pow2(x, n - 1);}double pow3(double x, int n){ double res = 1; while (n) { if (n & 1) { res *= x; } n >>= 1; x *= x; } return res;}double pow4(double x, unsigned int n){ if(0 == n) { return 1; } if(1 == n) { return x; } double tmp = (n & 1) ? x : 1; return tmp * pow4(x * x, n / 2);}int main(){ int startTime, endTime; startTime = clock(); for (int i = 0; i < COUNT; i++) { pow(2.0, 100); } endTime = clock(); printf("调用系统函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime)); startTime = clock(); for (int i = 0; i < COUNT; i++) { pow1(2.0, 100); } endTime = clock(); printf("调用pow1函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime)); startTime = clock(); for (int i = 0; i < COUNT; i++) { pow2(2.0, 100); } endTime = clock(); printf("调用pow2函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime)); startTime = clock(); for (int i = 0; i < COUNT; i++) { pow3(2.0, 100); } endTime = clock(); printf("调用pow3函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime)); startTime = clock(); for (int i = 0; i < COUNT; i++) { pow4(2.0, 100); } endTime = clock(); printf("调用pow4函数计算1亿次，运行时间%d毫秒\n", (endTime - startTime)); return 0;}

运行结果：

调用系统函数计算1亿次，运行时间222毫秒调用pow1函数计算1亿次，运行时间790804毫秒调用pow2函数计算1亿次，运行时间89706毫秒调用pow3函数计算1亿次，运行时间3320毫秒调用pow4函数计算1亿次，运行时间6874毫秒

从运行结果可以看出来，最快的是math.h提供的函数pow，接下来依次是pow3、pow4、 pow2，最慢的是pow1。

六、math.h中的pow函数源码

在网络上找到了一份微软的math.h源码 ，这里有关于pow函数的实现

template inline _Ty _Pow_int(_Ty _X, int _Y){ unsigned int _N; if (_Y >= 0) _N = _Y; else _N = -_Y; for (_Ty _Z = _Ty(1); ; _X *= _X) { if ((_N & 1) != 0) _Z *= _X; if ((_N >>= 1) == 0) return (_Y < 0 ? _Ty(1) / _Z : _Z); }}

这个实现思路跟pow3的实现思路是类似的。

七、结论

在实际编程时，可以直接调用math.h提供的pow函数；如果在特定场合需要自己定义的话，推荐使用pow4的方式。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。