【アルゴリズムの分析と設計】迅速なべき乗アルゴリズムの分析とjavaの実現

ACMの競争では、大きな数のモードのべき乗演算に関わる問題がよく現れます.例えば、2を解く10000乗モードの100000万九の結果は、有効なべき乗アルゴリズムを設計する必要があります.本論文では、上記の応用シーンを結合し、以下のいくつかの一般的なべき乗アルゴリズムを分析し、Javaコードの実現を与える.

再帰方法:二分高速べき乗(行列高速べき乗アルゴリズムともいう)

非再帰的方法:バイナリ変換法

二分急速べき乗
この方法の設計思想は簡単である:Aのn乗に対して、nが偶数の場合、A^n=A^(n/2)*A^(n/2);nが奇数の場合、A^n=A^(n/2)*A^(n/2)*A(ここでn/2が整数となります.)したがって、再帰的に解くことができる.時間の複雑さはO(lgn)である.ここではこれ以上話しません.コードを貼り付けます.

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

バイナリ変換法
以上の方法の効率は非常に高価な関数呼び出しのために高くない.ここではサイクルの方法で改善することを考えます.例を挙げます.
5の900乗位について:900=29+28+27+24+23+21=512+256+12+16+8+2ですので、計算は5900=52∗28_?5512に変換できます.以下の手順で解決できます.4∗5645256=5128∗5128 5512=5256∗5256
実は詳しく以下を考えてみます.数学の原理は最初の方法と同じですが、コードの実現レベルで最適化しました.コードを見てみます.

public static double pow(double a, int n){
    double res=1;
    while(n>0){
        if((n&1)==1){  //   n%2 != 0
            res *= a; 
        }
        a*=a;
        n>>=1;
    }
    return res;
}

long型の整数を定義すると、結果が2より大きい64乗がオーバーフローします.しばしば大きな数のべき乗問題が発生し、その結果をモジュラス処理します.公式a^n% m=(...(((((*a%)a%m**%m)…)a%mによって、上記のコードを以下のように改善します.

public static long pow(int a, int n, int m){  //m       
        long res = 1; 
        while (n > 0) { 
            if ((n & 1) == 1) 
                res = (res * a) % m; 

            a = (a * a) % m; 
            b >>= 1; 
        } 
        return res; 
  }