数学：快速求幂算法

本文转自CSND博客：http://blog.csdn.net/u013457107/article/details/20485619

原文如下：

快速求幂算法

参见了别人的博客http://blog.sina.com.cn/s/blog_3f2fa9610100soxb.html，了解到了快速求幂的一种方法，比简单的循环相乘要大大减少乘法次数，自己学习后写的c++代码如下

 1 bigint power(bigint x, int n)
 2 {
 3     bigint ret;
 4     ret.set(1);
 5     while (n!=0)
 6     {
 7         if (n&1==1)
 8             ret=ret*x;
 9         x=x*x;
10         n>>=1;
11     }
12     return ret;
13 }

这里用到了位运算，同时提高了运算效率。bigint数据类型是我自己定义的，可忽略。

接着上一步继续深入，当我们需要对一个很大的乘幂结果取模时，由于a*b%m=(a%m)*(b%m)的原理，可以将取模过程融入到快速求幂过程中，将代码稍加改进即可：

 1 bigint power(bigint x, int n, int k)
 2 {
 3     bigint ret;
 4     ret.set(1);
 5     while (n!=0)
 6     {
 7         if (n&1==1)
 8             ret=(ret*x)%k;
 9         x=(x*x)%k;
10         n>>=1;
11     }
12     return ret;
13 }

同样这也是从大神的博客学来的http://blog.sina.com.cn/s/blog_8619a25801010wcy.html。看来要想学好计算机，一定要好好学数学，这是读研的重要任务之一。