このブログの「プログラミング」カテゴリを見に来てくれている人がけっこういらっしゃるようで、それにもかかわらずまったく更新していないな～とか思っていました。最近、プログラミングをほとんどやっていないのでネタも出てこないのですが、やってなくてもネタは作れるだろということで、普段あまり考えることもない掛け算のアルゴリズムを取り上げてみることにしました。
なんでそんなことを唐突に書こうかと思ったか？話しは長くなるので省きますが、今担当している本で例外の話が出てくるのですが、オーバフロー例外といい観念的には「溢れたから例外なんでしょ」と理解していても、「溢れる」とはどういうことか？に始まって、最近は中身のことをよく知らずに言葉だけで理解したつもりになって、表向きの動作だけでプログラムを組むのが普通になっているよな、とちょっと寂しくなったからもあるのです。
まぁ、年寄りの僻みというか郷愁といいますか、そんなところから出ていますので、興味のない方は吹っ飛ばしてください。さて、本題に入りましょう。
掛け算とは乗算のことですが、そんなものにアルゴリズムが必要なの？という意見はごもっともでしょう。プログラム言語では乗算演算子を使えば一発で、別に何か特別なことをするということもありませんからね。では、乗算にアルゴリズムが必要なときがあったの？と聞かれれば、それはあったと答えるでしょう、私は。今では古典的な言語であるCやFORTRANでも乗算演算子は存在しましたが、CPUレベル、機械語レベルで見た場合には、乗算機能は必ずしも実装されていなかったからです。
たとえばx86アーキテクチャの祖である16ビットCPU・8086/8088（インテル）にはMUL命令、IMUL命令があり、整数の乗算を行うことができましたが、それ以前の8ビットCPUであるZ80（ザイログ），8080/8085（インテル）などには乗算命令はありませんでした。つまり、乗算機能を実現するには、何かプログラムを組むしかないわけです。Z80時代にもCやFORTRANはありましたから、乗算演算子を使ってプログラムを組まれた場合、それを何かに置き換える必要があった、というわけです。今回は、このような状況下でどのように乗算を実現したか、ということを書きたいと思っています。
悔しいことに6809には乗算命令があったのです。まあ、あとから出てきたんだから当たり前と言っておきましょう。フン！
私が8080でプログラムを組み始めたのは高校生の頃で、情報処理の基礎もない子供でしたから、掛け算をやりたいときには馬鹿正直に次のように考えました。
- 乗数Aと被乗数Bを用意する。
- 結果を入れるレジスタCを用意して0クリアする。
- Aが0でなければ、CにBを加える。
- Aを1減じる。
- Aが0でないなら3に戻る。
- Aが0になれば終わり。
要は、「被乗数を乗数分だけ足しまくる」という基本かつ原始的なものです。誰でも理解できるのが利点ですが、とてつもなく効率が悪いという欠点があります。計算時間は、乗数の大きさで決まってしまい、どのような計算でも一律の演算時間というのが期待できません。また、正負を別に考慮しなければなりません。最初に符号を切り離して絶対値をとるなどしないと、「Aを1減じる」という部分が不具合のもとになります（負数はいくら減じても負数のままで永久に0にならない）。
さて、情報処理を学び、数値データの内部表現などの基礎や演算の仕組みを知るようになってくると、もっとシンプルに掛け算が行えるのではないか、ということに気付きます。ご存じのとおり、コンピュータの内部ではあらゆるデータは0か1のビット列（2進数）で保持されており、数値データも例外ではありません。
ところで、我々が電卓などを使わずに掛け算を行うときには、どのようにしますか？筆算というやり方で、乗数と被乗数を二階建てにし、一桁ずつ掛け算を行って、各桁の結果を足し併せて全体の結果としていますよね。もちろん、このときにも各桁の掛け算という基本的な演算が行われているのですが、この掛け算ができないことには筆算がそもそも成り立ちませんね。
上で、Z80などには乗算命令がなかった、と書きましたが、実は基本的な乗算を行うことは可能だったのです。それは、単純に2倍する、という乗算です（1/2するという除算も可能）。正確には乗算とは呼ばずに、「シフト」と呼びます。シフトすれば、CPUの世界では2倍したことになります。話しを戻しますが、コンピュータの内部での情報記憶単位はビットであり、これは2進数の世界です。2進数では1桁が2の重みしか持ちませんから、2倍すれば桁が上がります。こう考えると、「シフト」と加算だけで筆算ができそうな感じがしてきませんか？
このように考えたかはわかりませんが、世の中には洗練された美しい乗算アルゴリズムがあります。それを紹介しましょう。
リンク：ブースの乗算アルゴリズム
ブース（Booth）のアルゴリズムでは、演算時間は乗数のビット数によってほぼ決まり、あとは数値データの内容（ビットパターン）で上下します。数の大小では決まらないので、演算時間を均質化できます。このアルゴリズムは、論理回路への実装が容易だったため非常によく使われていたそうです。今では、ほとんど意識されることはないそうです。
多くの処理が「機能」として実装されてしまうと、「機能」を使うことに終始して、その「機能」がどういった仕組みで実現されているかということは忘れがちになります。それはそれで結構なことなのですが、ブラックボックスかが進むことのデメリットもないわけではありません。ときには、我々のIT社会を支える基本的な計算処理について、思考をめぐらせてみるのも楽しいものではないでしょうか？
次回は、割り算（除算）行ってみます（ウソ）。
コメント