前回のあらすじ！
加算ってこんなに難しかったっけ(絶望)
BFではじめる円周率計算入門 #0 -問題設定と多倍長加算-
BFで九九ならぬB-1B-1をやってみる
前回と同じようにまずは1桁どうしの場合から乗算を考えていきます。
さて、$M\times N$は$M$を$N$回加算してください、という意味になります。
そのため前回加算ができている私たちは「$N$回繰り返すこと」を新たに考えれるだけで乗算はできそうです。
さて、1桁どうしの加算のコードは次のようでした。
- 被加数:0番地
- 加数:1番地
- キャリ:2番地
- 条件分岐終了タグ:3番地
> // 加数へ移動
[
- // 加数減算
> // キャリへ移動
+ // 「一旦」キャリ加算
<< // 被加数へ移動
+ // 被加数加算
[ // 被加数が0でなければ
>> // キャリへ移動
- // キャリの加算をなかったことにする
> // ループ脱出用メモリへ移動
]
<< // 加数へ戻る
]
「$0$に$M$を足すコードを$N$回繰り返したら終わり」と思ってしまうところですが、1度加算したあと, 加数のメモリの値は$0$になってしまうため、このままだと繰り返しを行うことができません。そこで加算するときに同時に加数をコピーするためのメモリを空けておいて一時保管し、復元する必要があります。
さて、では$M$をどのようにコピーするかですが、みなさん、$0+M=M$ですね。現在、「加数のデクリメントした分だけ被加数のインクリメントをする」ことで加算を実現しているのですが、$0$を格納したメモリを新たに用意して、「加数のデクリメントした分だけ被加数と(初期値ゼロの)コピー用変数のインクリメントをする」とすれば、2つの変数に対して同時に加算処理を行うことができるというわけです。
ちなみに被加数が$0$なので繰り上がりは発生しません。うれしいね。
これを追加すると、
- 被加数:0番地
- 加数:1番地
- 加数のコピー:2番地
- キャリ:3番地
- 条件分岐終了タグ:4番地
としたときのコードは次のようになります。
>> // コピー用変数へ移動
[-] // コピー用変数を0にする(コピー変数に対して、値が0になるまで減算処理をする)
< // 加数へ移動
[
- // 加数減算
> // コピー用変数へ移動
+ // コピー用変数加算
> // キャリへ移動
+ // 「一旦」キャリ加算
<<< // 被加数へ移動
+ // 被加数加算
[ // 被加数が0でなければ
>>> // キャリへ移動
- // キャリの加算をなかったことにする
> // ループ脱出用メモリへ移動
]
<<< // 加数へ戻る
]
/* 復元処理 */
> // コピー用変数へ移動
[
- // コピー用変数を1減らす
< // 加数へ移動
+ // 加数を1増やす
> // コピー用変数へ移動
]
上のコードのコメントを省くと下のようになります。
>>[-]<[->+>+<<<+[>>>->]<<<]>[-<+>]
さて、これで何度繰り返しても大丈夫なようになりました。
しかし、$N$回繰り返すからと言ってこれを手動でやりたくないですよね。
そこで$N$を保管しておくためのメモリも新たに用意します。
あとは、加算するたびに加算回数をデクリメントして、0になったら終わり、のコードを追加すれば終了です。お疲れさまでした。
- 被加数:0番地
- 加数:1番地
- 加数のコピー:2番地
- キャリ:3番地
- 条件分岐終了タグ:4番地
- 加算繰り返し回数:5番地
>>>>> //加算繰り返し回数格納位置へ移動
[
<<<<< //0番地から始める
>>[-]<[->+>+<<<+[>>>->]<<<]>[-<+>] //加算処理・加数復元
>>> //加算繰り返し回数格納位置へ移動
- //残り加算回数を1減らす
]
3行目と4行目のはじめで相殺できる場所があるため、簡潔にして、コメントを省くと下のようになります。
これが1桁どうしの乗算というわけですね。
>>>>>[<<<[-]<[->+>+<<<+[>>>->]<<<]>[-<+>]>>>-]
加算の繰り上がりと乗算の繰り上がり
さて、1桁どうしの乗算のコードを書いたわけですが、ひとつ引っかかる点があります。
それが「乗算の繰り上がりは加算の繰り上がりと同じにしていいか？」という点です。
結論から言うとこれは全く問題ありません。加算のお化けが乗算なので加算の繰り上がり処理の転用で問題ありません。
$9+9+9$をするときに$9$から$27$に向けてインクリメントし続けると$2$回繰り上がります($2$回$B^0$の位が$0$になるポイントが存在します)というのと同じことをしているわけなので。
また、繰り上がり値の上限についても$B$を超えることはありません。($(B-1)\times (B-1) < B^2$)
そのためこのコードで問題ないということがわかります。
※Tips $B$は基数
>>>>>[<<[-]>[->+>+<<<+[>>>->]<<<]>[-<+>]>>>-]
まとめ
加算を使えば「やること自体は」あまり難しくなかったという感じでしたが、コードの可読性はもう面影をなくしてしまいました。
さて、これで準備が整いました。次回、「大いなる敵†多倍長乗算†」それでは。