求a的b次方、a的b次方对m取模


 
  • 快速计算乘方的算法，求a的b次方


如计算2^13，则传统做法需要进行12次乘法，但是可以优化：
把2*2的结果保存起来看看，是不是成了：4*4*4*4*4*4*2 
再把4*4的结果保存起来：16*16*16*2 
一共5次运算，分别是2*2、4*4和16*16*16*2 

这样分析，我们算法因该是只需要计算一半都不到的乘法了。 
为了讲清这个算法，再举一个例子2^7：2*2*2*2*2*2*2 
两两分开：(2*2)*(2*2)*(2*2)*2 
如果用2*2来计算，那么指数就可以除以2了，不过剩了一个，稍后再单独乘上它。 
再次两两分开，指数除以2： ((2*2)*(2*2))*(2*2)*2 
实际上最后一个括号里的2 * 2是这回又剩下的，那么，稍后再单独乘上它 
现在指数已经为1了，可以计算最终结果了：16*4*2=128

  1. long my_power(long a,long b)  
  2. {  
  3.     long r=1; //用来计算"剩下的"乘积   
  4.     if(b==0)  
  5.         return 1;  
  6.     if(b<0)  
  7.         return 0;  
  8.     while(b>1)  
  9.     {// 一直计算到指数小于或等于1   
  10.         if((b&1)!=0) //判断p是否奇数，偶数的最低位必为0  
  11.             r*=a; // 若r为奇数，则把"剩下的"乘起来  
  12.         a *=a;// 主体乘方  
  13.         b/=2;// 指数除以2              
  14.     }  
  15.     return r*a;// 最后把主体和“剩下的”乘起来作为结果      
  16. }  


  • 求x的y次方对z取模(x^y)mod z：蒙格马利快速幂模算法
X^Y可以看作Y个X相乘，即然有积模分解公式，那么我们就可以把Y个X相乘再取模的过程分解开来，比如：(17^25))则可分解为：( ( 17 * 17 ) % 29 * ( 17 * 17 ) % 29 * …… 

如果用上面的代码将这个过程优化，那么我们就得到了著名的蒙格马利快速幂模算法：

  1. long Montgomery(long a,long b,long m)  
  2. {  
  3.     long r=1;  
  4.     a %=m;  
  5.     while(b>1)  
  6.     {  
  7.         if((b&1)!=0)  
  8.             r = (r*a)%m;  
  9.         a = (a*a)%m;  
  10.         b/=2;      
  11.     }  
  12.     return (r*a)%m;      
  13. }