快速幂取模

 

(2012-01-02 21:37:56)

 

快速幂取模

 

快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c 

因此很容易设计出一个基于二分的递归算法。

以下是我的代码，以下代码必须保证输入的是合法的表达式，比如不能出现0^0 mod b：

long  exp_mod( long  a, long  n, long  b)

{

long  t;

if (n == 0 )  return  1 % b;

if (n == 1 )  return  a % b;

t = exp_mod(a,n / 2 ,b);

t = t * t % b;

if ((n & 1 ) == 1 ) t = t * a % b;

return  t;

}

 

 

非递归：

ll pow_mod(ll a,ll n,ll m){

    int b = 1;

    while(n>0){

        if(n&1)b = (b*a)%m;

        n>>=1;

        a = (a*a)%m;

    }

    return b;

}

 

关于其中的一个按位与运算，来自百度知道的解释：

 

 

也就说，只有技奇数才满足这个条件  n&1==1

 

我的测试：

public class Test {

public static void main(String[] args) {

long a=3,n=100,b=2;

long t=exp_mod(a,n,b);

System.out.println(t);

System.out.println((int)Math.pow(3, 100)%2);

}

public static long exp_mod(long a,long n,long b)

{

long t;

if(n==0) return 1%b;

if(n==1) return a%b;

t=exp_mod(a,n/2,b);//注意这里n/2会带来奇偶性问题

// System.out.println(t);

t=t*t%b;//乘上另一半再求模

// System.out.println(t);

if((n&1)==1) t=t*a%b;//n是奇数，因为n/2还少乘了一次a

// System.out.println(t);

return t;

}

}