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

ゝ一世哀愁。 2022-05-23 07:05 223阅读 0赞

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

在math.h中，声明了一个函数pow(x, n)，用于求x的n次方。假如咱们不调用math.h中的pow函数，如何实现求x ^ n的算法呢？

# 一、非递归方法 #

#include <stdio.h>
    
    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.000000
    5 ^ 3 = 125.000000
    10 ^ 0 = 1.000000

# 二、递归方法1 #

#include <stdio.h>
    
    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 <stdio.h>
    
    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.000000
    5 ^ 3 = 125.000000
    10 ^ 0 = 1.000000
    3 ^ 19 = 1162261467.000000

# 四、快速幂递归解法 #

#include <stdio.h>
    
    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 <stdio.h>
    #include <math.h>
    #include <time.h>
    using namespace std;
    
    #define COUNT 100000000
    
    
    double 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源码 http://www.bvbcode.com/cn/z9w023j8-107349 ，这里有关于pow函数的实现

template<class _Ty> 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的方式。

了解信息学奥赛请加微信307591841（QQ同号）