【算法】新人学算法之一·快速求幂

接触ACM没几天，向各路大神求教，听说ACM主要是研究算法，所以便开始了苦逼的算法学习之路。话不多说，RT所示，学习快速求幂。

在头文件<math.h>或是<cmath>中，double pow( double x, double y );函数是用来快速求x^y，于是便从pow函数来说起，以下大体上是pow的函数代码：

int pow(int x, int n)
{
int num = 1;
while (n != 0){
num = num *x;
n = n -1;
}
return num;
}

通过以上程序，2^5 = 2*2*2*2*2的流程中一共进行了4次乘法。试想若是大数2^99999999.......，这样循环的算下来肯定要计算到猴年马月。那么我们有什么办法可以简化我们的幂指运算呢？

分析数据

2^4=2^2 * 2^2;

2^5=2^2 * 2^2 * 2

2^6=2^3 * 2^3

2^7=2^3 * 2^3 * 2

……

x^n = x^(n/2) * x^(n/2) (n为偶数）

x^n = x^(n/2) * x^(n/2) * n (n为奇数）

显然这种算法分析利用分治思想（divide and conquer）。通过这种方式，我们可以根据通项公式写出递归函数求分制幂指运算的函数代码：

int DC_pow(int x, int n)
{
if (n==1) return x;
if (n==0) return 1;
else if (n & 1) return DC_pow(x,n/2)*DC_pow(x, n/2)*x; // 对应公式x^(n/2) * x^(n/2) * n
else return DC_pow(x,n/2)*DC_pow(x, n/2); // 对应公式x^(n/2) * x^(n/2)
}

由此我们以分治思想，减少了运算量。接下来，我们研究此递归代码的一些细节。对于n/2，我们在二进制位运算中还有其他的处理方式，倘若一个数是二进制数，只要我们将该数右移一位(x>>1)，即可对其真值除以2。也许你又会想，DG想表述的是什么意思，即使我把代码中的n/2换成n>>1运算量有没有改变，到底意义何在呢？我们从一个例子引出：

问题：请求出3^999=？（问题目的在于感受不同求解方法的复杂程度）

分析：我们先调用最最基本的方式进行求解，即为求:3 * 3 * …… * 3(999个3)，这样一共要进行998次乘法运算。这种方法显然是太麻烦，反复的递归，计算机心里定会默念“我靠，坑爹啊！”

接下来，我们使用简单分制思想来做此题，这样就可以大大简少运算次数，使得计算次数仅为9次。但是，如果你也在学习ACM的话，你会懂得递归做法运行速度之慢。即使递归函数通俗易懂，即使写法简单，但是并不推荐。你若不信，我给大家举一个简单的例子：

利用欧几里德算法（辗转相除法）计算两数的gcd（最大公约数）

递归形式：

1. int gcd(int a,int b)
2. {
3. if(a == 0) return b;
4. else return b == 0?a:gcd(b,a%b);
5. }

非递归形式：

1. int gcd(int a,int b)
2. {
3. int c;
4. if(a == 0) return b;
5. while(b!=0) c = b,b = a % b,a = c;
6. return a;
7. }

以上利用相同的思想进行求解a，b的gcd，但是效率有很大偏差，大家可以尝试。

那么，还有什么方法来求解这个问题呢，接下来便是经典的快速求幂法。我们将3^999进行分解，即为： (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3。这时候，我们可以整理出3的指数部分形式：2^9+2^8+2^7+2^6+2^2+2^1+2^0。然后，我们再把999转换成2进制为1111100111，2进制的转换作为指数位置的数。由此，我们同样的利用了分治思想，将指数分成了2的n次方和的形式。配合上右移运算，我们只要将其二进制数与1做与运算，为真则将此位上的2^n次方加入，为假则不加入。下面放出代码：

int spow(int x, int n)
{
int result = 1;
while (n > 0)
{
if (n & 1) result *= x;
x *= x;
n >>= 1; //n=n/2
}
return result;
}

以上便是全部内容，第一次发文，多有错误。多多包含。

学习本块知识参考过的博文：

http://blog.csdn.net/zhizichina/article/details/7573342

http://blog.csdn.net/hkdgjqr/article/details/5381028

关于快速求幂的ACM题集：

HDU1575、HDU1852、HDU2817、HDU2035.