a la russe法による乗算アルゴリズム

忙しすぎてネタを書く時間がない。しかし時間は作るものらしいので、日々の生活をちょっとずつ切り詰めて余暇を作る。

乗算アルゴリズムの話。もし加算とビットシフトしか無かった場合、いかにして効率良く乗算を行うか？

単純な方法

a * bは、「aをb回足したもの」といえる（話が面倒になるので、a、bは非負整数とする）。そこで、その考えをそのままコードに落としてみる。

int mul(int a, int b) {
    int sum = 0;

    if (0 == b) return 0;

    while (b != 0) {
        sum += a;
        b--;
    }
    return sum;
}

計算量をざっと見積もる。
ループ部分の条件分岐がb+1回、加算がb回、デクリメントがb回。bに比例した計算コストがかかるように思われる。

a la russe法

多くのアーキテクチャでビットシフトは高速に実行できるから、うまくすれば計算量を削減することができる。表題のa la russe法は、ビットシフトを巧妙に使う。

a * bを計算するとき、aが偶数であれば、aを半分、bを2倍しても計算結果は変わらない。例えば 4 * 10は(4 / 2) * (10 * 2)すなわち2 * 20と同じ。この半分と二倍という操作がポイントで、2進数を使う多くのコンピュータでは、ビットシフトで実現できる。
それではaが奇数の時はどうするか。ひとつ値を「どける」ことでまた偶数にすれば、上述の変形ができる。すなわちa * b = (a - 1) * b + bとする。a - 1は偶数だから、a - 1とbに対して1.のビットシフト操作ができる。

この二つの操作を繰り返すと、いずれaは1となる。その時のbの値と、「どけた」分の値を足すことで乗算結果が得られる。
具体例として、35 * 21をやってみる。

35 * 21 = 17 * 42  + 21
        =  8 * 84  + 42 + 21
        =  4 * 168 + 42 + 21
        =  2 * 336 + 42 + 21
        =  1 * 672 + 42 + 21
        =  672 + 42 + 21
        =  735

Cで実装するなら、こんな感じになるはず。

int mul(int a, int b) {
    int sum = 0;

    if (0 == a) return 0;

    while(a != 1) {
        if (a & 1) sum += b;
        a >>= 1;
        b <<= 1;
    }
    return sum + b;
}

さてさて、この場合の計算量はどれほどだろうか。

ループの終了条件である $a$ は、反復一回ごとに右に1だけシフトされるから、反復回数はおおむね $\log_{2}{a}$ となるだろう。 $sum$ に $b$ を加算する部分の実行回数は、 $a$ にいくつビットが立った部分があるかによる。平均して1が半分だとすれば、 $(\log_{2}{a})/2$ 回実行されると予想できる。その他、最初の $a$ がゼロ判定と最後の加算がある。