繰り返し2乗法

冪乗を高速に計算できるらしい。 ”2の冪乗” 乗までは自乗の自乗の自乗……といったふうに計算して, それに残った分を掛けると素直にループ回すよりも少ない回数で計算できるよね, という発想に見える。

ab 乗を計算する場合だとこんな感じかと(動作確認はしてない ゴミ)。

unsigned int pow (unsigned int a, unsigned int b) {
    unsigned int ret = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            ret *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ret;
}

標準ライブラリの関数ってかなり洗練されているイメージがあるので,pow(3) 使った方が速い説はあるなあ……。 あーでもあれは負数乗とかも処理できる関数だから遅いんだろうか……。

参考(になりそうなリンク)