累乗計算の高速化

プログラミングの練習問題に累乗計算があったのでメモ．

条件は，以下のとおり．

• a^nの2つの引数を使った関数（メソッド）を用意し，計算結果を表示する
• 最初は，for文などで実装
• 次に，O(log(n))になるように実装

最初のfor文使うやつは簡単．プログラミングやったことある人なら，たいていできる．

次の計算量を減らすやつが大変．

まず，最初のプログラムでは，計算量はO(n)．
つまり，n回の計算処理をするということになる．

これをどうやってO(log(n))にまで落とし込むか？

最初は安易にnを2で割って，2つの値同士を計算すればいいと考えた．
つまり，2^10 = 2^5 * 2^5 = 1024と考えたわけだ．
でもこれ，安易すぎる．．．
計算量だって単純にO(n/2)，実質O(n)だ．
これじゃあたいして意味がないじゃないか．

着眼点は悪くない，たぶんnの値を2の累乗の形にして表して，計算すればいいはずだ！
と思ってアクセクしたけど，いいアイディアも浮かばず．結果的に調べました．

まぁ，練習問題になるくらいだし，アルゴリズムは出来上がってるのが普通．調べたら，やっぱりありました，累乗の高速化アルゴリズム．

詳しいことはGoogleなりなんなりで調べれば良い．

とりあえず，アルゴリズムは以下のようになる．

power(a, n)

• n == 0  | = 1
• if  even n      |  n = n/2 , power(a*a, n)
• else if odd n  |  a*power(a, n-1)

これにしたがって実装(Rubyを使用)してみた．
これはすごい．計算回数をカウントしてみたところ，2^100の処理がたったの9回になった．
そのほかのパターンでも，大幅に処理回数が減った．
みごと，O(log(n))になった．

めでたしめでたし．良い練習問題だった．