algorithm - べき乗のための分割統治アプローチ？

Question

宿題として、大きな整数のべき乗のための分割統治アプローチを実装する必要があります。カラツバの乗算アルゴリズムを知っていますが、両方とも大きな整数であるx ^ yの結果を取得するために、どの分割統治アルゴリズムを適用できますか？

Answer 1

square とmultiplyという名前でグループ化されたアルゴリズムがいくつかあります。彼らからインスピレーションを得ることができます。

Answer 2

x^256 を考えてみましょう。を実行する代わりに、 x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x(...(((x^2)^2)^2...)^2 を 8 回 (log2 of 256) 実行できます。

一般に、指数を 2 進数として書き出し、指数の和の規則を適用します。次に、x の累乗を計算するとき、それらが指数に表示される場合は累算器に乗算します (指数のその桁に「1」がある場合に表示されます)。

http://en.wikipedia.org/wiki/Exponentiation_by_squaringを参照してください。

Answer 3

これは素晴らしい再帰アルゴリズムです。

int pow(int a,int b)
{
    if(b == 0) return 1;
    else if(b % 2 == 0) return pow(a,b/2) * pow(a,b/2);
    else return a * pow(a,b-1);
}