ロシア農民のかけ算とCPU

JavaScript

ロシアの農民のかけ算という、かけ算の方法があるらしい。

たとえば9×12ならば、前の数を半分にしていき、後の数を２倍していく。

9  12
4  24
2  48
1  96

前の数が２の倍数になってるものを削除して

9  12
1  96

残った後ろの数を足すと

12 + 96 = 108

あら不思議、9×12の答えになったよコレ。

このロシアの農民のかけ算が何をしているのか調べてみると

9 * 12 = (4 * 2 + 1) * 12 
       = (4 * 2 * 12) + 12
       = (4 * 24) + 12
       = (2 * 48) + 12
       = (1 * 96) + 12
       = 96 + 12

な感じに分配法則やら結合法則やら中学校一年で習うような数学テクを使った計算をルーチン化しているものだった。

２倍や半分はシフト演算でできるし、偶数奇数は最下位ビットを見れば分かるので簡単にプログラミングできそう。JavaScriptでこのかけ算アルゴリズムを実装してみると

function multiply(a, b) {
   var c = 0;
   while(a > 0){
       if (a & 1 == 1) c += b;
       a >>= 1;
       b <<= 1;
   }
   return c;
}

と非常に簡単に書ける。あまりにも簡単なので、もしかしてCPUもこうやってかけ算しているのでは？と思い、調べてみると、CPUの乗算器はほとんどこのアルゴリズムと同じだった。ロシア農民、すごいではないか。