効率的なべき乗演算

参考:データ構造とアルゴリズムの分析-Java言語の説明
(米)Mark Allen Weiss
       整数のべき乗XNを計算する   の一般的なアルゴリズムはN-1を用いる 二乗自乗しかし、より良いアルゴリズムを見つけることができます.Nが偶数の場合、XN=XN/2*XN/2  , Nが奇数の場合、XN=X(N−1)/2*X(N−1)/2*Xがある.
       このアルゴリズムがなぜより効率的なのかを説明するために、例を挙げます.例えばX 62の計算    ,最初の一般的なアルゴリズムで61回の自乗をします.2番目のアルゴリズムでは9回の乗算を行います.
        X3=(X2)X  ,  X7=(X3)2X  ,  X15=(X7)2X  ,  X31=(X15)2X  ,  X62=(X31)2
         X 3を求めるから   X7 X15 X31 それぞれ2回ずつ乗算して、最後にX 62を求めてまた1回乗算して、全部で9回です.
         コードは次のとおりです.     

     public long pow(long x,int n){
		
		if(n==0)
			return 1;
		else{
			
			//  n   
			if(n%2==0)
				return pow(x*x, n/2);
			else 
				return pow(x*x, (n-1)/2)*x;
			
		}
	}

         べき乗演算で得られる数は大きいかもしれません.任意の大きな整数を処理するためにjavaのBigIntegerクラスを使用することができます.上記のコードを変更します.

	public BigInteger pow2(BigInteger x,int n){
		
		if(n==0)
			return BigInteger.valueOf(1);
		else {
			if(n%2==0)
				return pow2(x.multiply(x), n/2);
			else 
				return pow2(x.multiply(x), (n-1)/2).multiply(x);
			
		}
		
	}

~完~