前回までのあらすじ！
乗算の陥落
BFではじめる円周率計算入門 #3 -多倍長乗算-
乗算終わったけどどうするの？
四則演算はあと2つ残っています。減算と除算です。除算は減算のお化けなので今回は減算をできるようにしていきます。
オーバーフローの活用術
2進数の減算では主にこの2つを用いて減算を加算として扱いました。
- 減数のビット反転値を加数として被減数と加算する
- さらに1を加算する
ここで「補数」とかいう話が出てきますが、自分自身いまだに補数ってなんですか？状態なのでこの単語そのものを使わずに説明します。
では、B進数の減算としてここからは話していきます。型とか扱ったことがある人は分かると思いますが、例えばunsigned char型に256を突っ込むとどうなるでしょうか。unsigned char型で扱える数は255までなので、256を渡そうとするとオーバーフローして格納されている値は0になります。同じように、「1桁の」$B$進数で表せる数は0から$B-1$までです。ここに$B$を入れようとすれば、オーバーフローして値は0となります。このように, オーバーフローという名前の$\mod B$($B$で割った余りを出す)処理が自動で掛かっている訳です。
つまり、1桁どうしの加算を行うとき、繰り上がりを考えなければ基数Bを足しても被加数が変化しないということになります。日付の変化を考えなければ4時の24時間後も48(=+24+24)時間後も4時なのと同じです。
本題に戻ります。1桁の$B$進数$M$から同じく1桁の$B$進数$N$を引く減算を考えるとき、$B$を一度加算しておいても変化しないため、$N$を引く動作は$B-N$を足す動作と変わらないことになります。さらに、1桁の$B$進数は$B$よりも必ず小さい値なのでこの加算は必ず正数どうしになります。2進数の減算も結局はこれと同じことをしているだけです。ビット反転が$B-1-N$の計算、ただし、余計に$-1$した分だけ後で足しているということになります。
これを使えば減算はできそうです。$D$桁の$B$進数で表せる数は$B^D-1$までなので、今回は$B^D$進数の減算になります。
$B^D-1$は、$D$桁すべてが$B-1$になったものなので、そこから減数$N$を引き、$B^D-1-N$を作ります。そして、被減数と作った数を加算して最後に埋め合わせのため$1$を足せばよい訳です。ここで、$B^D-N$を計算すれば1の足し引きしないから楽じゃないですかという話が出るかと思いますが、「$B^D-1$は、$D$桁すべてが$B-1$になったもの」というのを思い出してもらうと、各桁の最大値が$B-1$のため、唯一ある減算処理で繰り下がりを必要としないことになります。そのためこの方が都合がいいというわけです。
さて、これで基本の方針が定まりました。ただもう一つ検討すべき材料があるので実装は待ってください。
被減数と減数の大小比較 -減算を別の視点で見る-
そうです、符号の問題が残っています。符号なし型だから気にしなくていいんじゃないですかとか言わないでください。除算の話で必要になるのでここはちゃんとしておきましょう。
とは言っても、さっきの話をもう少し深掘りするだけです。
先ほど、減算ではこのようにやるといいました。
1桁の$B$進数$N$を引く減算を考えるとき、$B$を一度加算しておいても変化しないため、$N$を引く動作は$B-N$を足す動作と変わらないことになります。
あれ、引き算でその桁に$B$を足す処理ってどこかで......これが繰り下がりそのものです。
つまり、これは繰り下がりの前借りと考えることができます。皆さんは引き算を筆算でやるときにその桁どうしを逐次比較して、繰り下がりが必要な時にだけ「使うから頂戴」としているわけですが、「まあ使うかわからないけどさ、一旦頂戴」というのが今やってることです。では、使わなかった場合どうなるか？ という話ですが、これが加算時の繰り上がりになります。よくできてますね。
詳しく見ていきます。桁借りでもらう$B$よりも各桁の減数は絶対に小さいので、もらう値の方が大きいため桁借りしていればその桁はもとより大きくなるはずです。逆に桁借りしなくても計算できる場合にはその桁の値は減算前より小さくなるはずです。加算では繰り上がりが起こらない場合にはその桁はもとよりも大きい、つまり借りている訳になります。反対に繰り上がりが起こるということはその桁は減算前よりも小さいため桁借りした分を返却しているわけです。
つまり、今回の「$B^D$進数の減算」での符号は、最大桁の加算で発生するキャリの有無だけでわかることになります。
さて、これで準備が整いました。それでは実装に入っていきます。
多倍長減算
まずは原材料として、#2のおまけの多倍長加算のコードを用意します。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
メモリの内訳はこのようになっていました。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~30番地: キャリ
- 31~41番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:40-N番地, カウンタ領域: 41-N番地)
さて、料理の手順は2Stepです。ここにも0桁目にキャリ加算を適用したことが生かされます。
- 減数用メモリを用意し$B^D-1-N$計算
- 0桁目加算時のキャリを1に設定する
- 加算のコードを最後にペースト
では、減数用メモリを42-51番地にとりましょう。名前も減算用に変更します。
- 0~9番地: 被減数
- 10~19番地: 減数の反転値
- 20~30番地: キャリ
- 31~41番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:40-N番地, カウンタ領域: 41-N番地)
- 42-51番地: 減数
すると、$B^D-1-N$計算コードはこのようになります。ただし桁ごとの繰り返し処理については32-41番のカウンタ領域を利用して行います。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //カウンタ@41番地
//減数反転値の初期設定
++++++++++
[
//減数反転値N桁目へ移動(左22)
<<<<<<<<<<<<<<<<<<<<<<
//255に設定
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
+++++++++++++++
//戻る(右22)
>>>>>>>>>>>>>>>>>>>>>>
//カウンタ更新&左移動
-[-<+>]<
] //終了時@32番地
//カウンタ初期設定@41番地
>>>>>>>>>++++++++++
//減算処理
[
// 減数N桁目へ移動(右10)
>>>>>>>>>>
//減算 (距離32)
[- >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+ <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<]
// カウンタへ移動(左10)
<<<<<<<<<<
//更新
-[-<+>]<
] //終了時@32番地
キャリについては1に設定するだけなので簡単です。最終的に10桁どうしの多倍長減算のコードはこのようになりました。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //カウンタ@41番地
//減数反転値の初期設定
++++++++++
[
//減数反転値N桁目へ移動(左22)
<<<<<<<<<<<<<<<<<<<<<<
//255に設定
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
+++++++++++++++
//戻る(右22)
>>>>>>>>>>>>>>>>>>>>>>
//カウンタ更新&左移動
-[-<+>]<
] //終了時@32番地
//カウンタ初期設定@41番地
>>>>>>>>>++++++++++
//減算処理
[
// 減数N桁目へ移動(右10)
>>>>>>>>>>
//減算 (距離32)
[- >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+ <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<]
// カウンタへ移動(左10)
<<<<<<<<<<
//更新
-[-<+>]<
] //終了時@32番地
// キャリ設定@30番地
<<+
//加算!!
>>>>>>>>>>>++++++++++ //30番地 to 41番地
[
<<<<<<<<<<<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
] //@32番地
これで完成です。いつものようにコメントのないパターンも載せます。お疲れ様でした。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++
>>>>>>>>>>>>>>>>>>>>>>
-[-<+>]<
]
>>>>>>>>>++++++++++
[
>>>>>>>>>>[->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<]<<<<<<<<<<-[-<+>]<
]
<<+
>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
まとめ
今回はどっちかというと理論的な話が多かったです。加算から減算への変換は意外に簡単にできました。
次回、除算のはじまり。それでは。(明日3/14とかいうんじゃない)