アルゴリズム

ロシア農民の掛け算とその発明者

More than 1 year has passed since last update.

アルゴリズムを知的活動の産物と考えるのなら、文学や音楽のように作品自体に作者の何かが反映されていると考えるのはそれほど不思議なことではありません。ここではロシア農民の掛け算を例に取り、当時のこのロシア農民について思いを馳せたいと思います。

ロシア農民の掛け算

ロシア農民の掛け算(Russian Peasant Multiplication)とは、掛け算アルゴリズムのバリエーションの一つです。具体的に$4 \times 1234$を計算(筆算)してみます。まず、4と1234を、間に数値を入れられるよう並列し、左側を2倍、右側は半分にして行きます。右側を半分にする際、あまりが出る場合は、中央列に1を出ない場合は0を入れ、右列最下位が1になるまでこの操作を行います。最後に中央が1になっている行の左側を足し合わせて答えとします。一見するとすごい面倒なことをしている感じですね。

   4|0|1234
   8|1| 617
  16|0| 308
  32|0| 154
  64|1|  77
 128|0|  38
 256|1|  19
 512|1|   9
1024|0|   4
2048|0|   2
4096|1|   1

8 + 64 + 256 + 512 + 4096 = 4936 = 4 * 1234

これで何故計算がうまくいくのか不思議ですが、このアルゴリズム発明者にとっては必然の方法だったことが後ほど分かります。なお、この処理をプログラム言語で書くと面白いことに繰り返し演算の最適化#加法に一致します。

ロシア農民の掛け算(2進法バージョン)

さて、このアルゴリズムは2で割ったり掛けたりが頻出しますので、2進法で考えるのが良さそうですね。上記例の筆算を2進法で書き換えてみます。

          100|0|10011010010
         1000|1| 1001101001
        10000|0|  100110100
       100000|0|   10011010
      1000000|1|    1001101
     10000000|0|     100110
    100000000|1|      10011
   1000000000|1|       1001
  10000000000|0|        100
 100000000000|0|         10
1000000000000|1|          1

1000 + 1000000 + 100000000 + 1000000000 + 1000000000000
= 1001101001000
= 100 * 10011010010

2進法にすることで色々なことが見えてきます。まず、一番左列は1ビットずつ左シフトしているだけですね。逆に最右列は右シフトしているだけです。また、中央列の余りは結局最右列の最下位ビットになっているのでわざわざ書くまでも無いかもしれません。このように2進法にすると桁数は長くなりますが、10進法に比べ計算が格段に簡単になりました。しかし、これだけではなぜこのアルゴリズムがうまくいくのか見えてきません。そこで発想を転換し、最後の等式1001101001000 = 100 * 10011010010を小学校で習った掛け算の筆算で導いてみましょう。

掛け算の筆算(2進法バージョン)

私たちは小学校で、明示はされませんでしたが、10進法で筆算を習いました。実はこの筆算は何進法でも適応できることが証明できます。細かい証明は他に譲りますが、アイデアは次の例のように、分配法則をしているだけです。

 123
*  9
----
  27
 18
 9
----
1107

$123 \times 9$
$= (3 \cdot 10^0 + 2 \cdot 10^1 + 1 \cdot 10^2) \times 9$
$= 3 \cdot 10^0 \times 9 + 2 \cdot 10^1 \times 9 + 1 \cdot 10^2 \times 9$
$= 27 \cdot 10^0 + 18 \cdot 10^1 + 9 \cdot 10^2 $

分配法則自体はその数が何進法で表されてるかとかローマ数字で表されているとかオレオレ表記法といった表現とは独立していますので、任意進法で成立することがわかります。
そこで、2進法の100 * 10011010010を筆算で計算しています。

          100
* 10011010010
-------------
            0
         1000
          0
         0
      1000000
       0
    100000000
   1000000000
    0
   0
1000000000000
-------------
1001101001000

1で掛ける場合は冗長ですが一桁目まで0を入れています。さてこれから何が分かるでしょうか? 1000 + 1000000 + 100000000 + 1000000000 + 1000000000000が見事にロシア農民のアルゴリズムと一致しています。実は、

ロシア農民の掛け算 = 2進法で筆算

なのでした。これはよく考えてもらえれば、両者とも本質的には同じことをやっていることが見えてくると思います。これでロシア農民の掛け算がなぜうまくいくかはわかりました。

10進法のわけ

ところで、私たちは何故10進法を使うのでしょうか? 学校で習うからでしょうか? 過去人類は今日でも時計に痕跡のある12進法やらシュメールの60進法やらを使っていた時期もあったようですが、現時点では10進法が主流になっています。子供のとき数える際は文字通り指折り数えるわけですから、指が10本の私たちにとって12進法やら60進法は直感に反するのかもしれません。それで10進法が生き残ったと言えるでしょう。ここで興味深いのは、もし人類の指が8本だったらコンピュータに関する誤解やトラブルがかなり減っただろうということです。0.1が10進法では有限小数で2進法だと無限に循環する(=正確に表せない)なんて、普通の人は思いもよらないでしょうからね。もちろん、人類の指が何本であってもコンピュータは2進法で設計される前提ですが。天の微妙な配剤が招いた混乱と言えるでしょう。

ロシア農民おそロシア

ここからネタに走っていくわけですが、それにしてもこのロシア農民はどうしてこんな奇妙なアルゴリズムを考えたのでしょうか? 間違いなく言えることは彼は2進法に精通していた、2進法に日頃から慣れ親しみがあったということです。なぜなら、ロシア農民掛け算は10進法ではそれほど効力が無いからです。2進法で計算して初めて威力を発揮します。このアルゴリズムができた頃は当然コンピュータなんてないでしょうから、2進法を選ぶ何かしらの必然があったと考えられます。ここでは2つの説を考えます。まずは我々が10進法を使う類推で、指が2本だった説です。

指2本説

これはかなり有力そうです。遺伝か何かの影響でその人は指2本で生まれてきたとかです。そして指が2本の彼にとって10進法は馴染めないものであり(ちょうど我々が7進法に馴染めないのと同様)、2進法の筆算をしていた彼の計算を見た10進法話者が、この奇妙な掛け算を「ロシア農民の掛け算」と命名したのかもしれません。しかし、この説の致命的な欠点は、その指の少なさにあります。指が2本=片手に1本ですから、鉛筆が持てず筆算ができないことになります。

宇宙人説

これが、学会ではまだ受けられていませんが、私が最も支持したい説です。宇宙人であれば、遠い星から地球にたどり着いたことから、非常に高度な技術を持っていたと考えられます。当然コンピュータも発明済みでしょう。そして、それは2進法で動くようになっているはずです。彼らは元々別の進法を使っていたかもしれませんが、コンピュータとの最大限のシナジーを得るため2進法に宗旨変えした可能性が高いです。当然コンピュータを体内に埋め込んだりもしてるでしょう。これならば、ロシア人農民に変装した宇宙人の掛け算だったということで納得される向きも多いのではないでしょうか。しかし、それほど高度な技術を持っていたのなら、何故もっと効率の良いカラツバ法等を使わなかったのか疑問が残ります。

まとめ

ロシア農民の掛け算は、結局2進法で筆算をしているのと同じでした。そしてこのアルゴリズムの発明者は宇宙人である可能性が高そうです。このように、アルゴリズムそのものから発明者の人物像を浮かび上がらせることが可能です。