快速求幂(Quick Exponentiation)

时间:2023-12-06 16:12:02

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

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

  1. int pow(int x, int n)
  2. {
  3. int num = 1;
  4. while (n != 0){
  5. num = num *x;
  6. n = n -1;
  7. }
  8. return num;
  9. }

通过以上程序,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)。通过这种方式,我们可以根据通项公式写出递归函数求分制幂指运算的函数代码:

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

由此我们以分治思想,减少了运算量。接下来,我们研究此递归代码的一些细节。对于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次方加入,为假则不加入。下面放出代码:

  1. int spow(int x, int n)
  2. {
  3. int result = 1;
  4. while (n > 0)
  5. {
  6. if (n & 1)   result *= x;
  7. x *= x;
  8. n >>= 1;        //n=n/2
  9. }
  10. return result;
  11. }

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

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

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

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

关于快速求幂的ACM题集:

HDU1575、HDU1852、HDU2817、HDU2035.