前回までのあらすじ！
加算
BFではじめる円周率計算入門 #0 -問題設定と多倍長加算-
繰り返し活用編
BFではじめる円周率計算入門 #1 -1桁どうしの乗算-
BFではじめる円周率計算入門 #2 -加算の簡略化-
おことわり
今回は記事が長くなるのでBFで蕁麻疹が出るタイプの人は注意してください
BF式筆算
一度10進数に限定して話を進めます。
さて、#1では1桁どうしの乗算をしました。
この時、例えば$8\times 9=72$を実現するために、$0$に$8$を9回加算し、$(carry, sum)=(7, 2)$として出力しました。
筆算をこれと照らし合わせてみます。例えば、$123\times 456$を計算するとき筆算だと次のようになります。
\begin{array}{rrrrrr}
&&& 1 & 2 & 3\\
\times \large{)}&&& 4 & 5& 6\\
\hline
&&& 6 & 12 & 18\\
&& 5 & 10 & 15 & \\
+ \large{)}&4 & 8 & 12 & & \\
\hline
& 4 & 13 & 28 & 27 & 18 \\
\hline
& 5 & 6 & 0 & 8 & 8 \\
\end{array}
ちょっと変だと思う人が多いはずです。実際には掛け算の時に同時に繰り上がり処理をしているはずです。
繰り上がりは後にして、一旦上の式の意味を考えてみます。
さて、$k$桁の10進数$M=(M_k, M_{k-1}, \cdots M_0)$, $N=(N_k, N_{k-1}, \cdots N_0)$の乗算はこのようになります。
N = N_0 \cdot 10^0 + N_1 \cdot 10^1 + \cdots + N_k\cdot 10^k = \sum^{k}_{i=0}N_i\cdot 10^i
M \times N = M\sum^{k}_{i=0}N_i\cdot 10^i = \sum^{k}_{i=0}MN_i\cdot 10^i
では、ここからはB進数に拡張して考えていきましょう。
上の式にくっついている$10^i$について, 10進数なので$10^i$であるため, B進数では$B^i$になります。
$B$進数における$B^i$の意味は左に値を$i$回シフトしなさいという意味です。
そのため, 筆算を行ごとに見ると最初は0シフト, 次は1シフトというようになっているわけになります。
つまり、$k$桁どうしの乗算は「シフトをしながら」$k$桁と$1$桁の乗算をしていけばできることになります。
また, $k$桁と$1$桁の乗算も$k$桁どうしの加算により実現することができます。
最後に繰り上がりについてですが、ここまでくれば「繰り上がり」はほとんど気にする必要がないことがわかります。
なぜなら結局乗算は加算とシフトでできてしまうためです。加算の繰り上がりをそのまま利用します。
さて、方針が固まりました。ではコードを実装していきます。
多倍長乗算の準備 - k桁と1桁の乗算 -
#2の最後(おまけ)の10桁どうしの加算コードを用意します。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
メモリの内訳はこのようになっていました。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~30番地: キャリ
- 31~41番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:40-N番地, カウンタ領域: 41-N番地)
まずは, #1を応用して, 繰り返しこれが加算できるよう準備をします。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~29番地: 加数のコピー
- 30~40番地: キャリ
- 41~51番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:50-N番地, カウンタ領域: 51-N番地)
// 51番地へ移動
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
// 10回繰り返す
[
// 加数N桁目へ移動(左32)
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
- //加数デクリメント
>>>>>>>>>>>>>>>>>>>>+ //キャリの一時インクリメント
<<<<<<<<<<+ // add: コピーメモリインクリメント
<<<<<<<<<<+ // 被加数インクリメント
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>] // (非ゼロ時)キャリデクリメント 終了時: フラグ領域
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< //加数位置へへ戻る
]
>>>>>>>>>> // @コピー領域
[-<<<<<<<<<<+>>>>>>>>>>] //計算済みの桁を復元
>>>>>>>>>>> //@キャリN minus 1桁目
//キャリ加算処理
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
上のコードのコメントを外すと下のようになります。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
では、繰り返しを追加してk桁と1桁の乗算を実装していきます。
これは繰り返しの実装だけなので説明は省略します。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~29番地: 加数のコピー
- 30~40番地: キャリ
- 41~51番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:50-N番地, カウンタ領域: 51-N番地)
- 52番地: 加算全体の繰り返しカウンタ
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //52番地
[
<++++++++++ //51番地
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
] // 終了後の(桁加算用)繰り返しカウンタ位置: 42番地
>>>>>>>>>>- // (加算全体用)繰り返しカウンタ@52番地デクリメント
]
本編 -多倍長乗算-
さて、ついに本番です。多倍長乗算の実装をしていきましょう。
2桁目以降は, 加算する数を左シフトする必要があるので, まずはシフト処理を記述していきます。
BFの性質上, コピーをするとコピー元が破壊されてしまうため(それってコピーじゃなくて移動じゃないんですか？), 左シフトの場合には最上位の桁から処理をする必要があります。したがって, シフトのコードはこのようになります
// 事前に10番地へ移動しておく
// 最上桁の破壊
[-]
// 上から2桁目 to 最上桁
>[-<+>]
//あとは「右へ移動して左へ値を移す」動作を繰り返す
>[-<+>]
>[-<+>]
>[-<+>]
>[-<+>]
>[-<+>]
>[-<+>]
>[-<+>]
>[-<+>]
「桁ごとの」繰り返し処理をしたいため, 52-61番地を活用して繰り返し処理の形に変換します。
//事前に10番地へ移動しておく
// 最上桁の破壊
[-]
// 52番地へ移動(処理桁が右へ移動していくため対応してカウンタメモリも52番地から60番地へずれていく)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
// 9回繰り返す
+++++++++
[
//11 plus N番地へ移動してコピー処理
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[-<+>]
// 戻る
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
// カウンタ更新&右移動
-[->+<]>
]
さて、ここで,最上桁を破壊する操作を付け加えました。これはオーバーフロー対策です。$k$桁どうしの乗算結果は最大$2k$桁ですが、これを$k$桁に収めると確実にオーバーフローします。そのため第9桁の左シフト後は第10桁目で確実にオーバーフローするため事前に切り捨てるというわけです。
今までのメモリ領域の説明をまとめると次の通りです。名称も乗算用に変えましょう。
- 0~9番地: 計算結果
- 10~19番地: 被乗数
- 20~29番地: 被乗数のコピー
- 30~40番地: キャリ
- 40-51番地: フラグ・カウンタ用領域
- 40-50番地: 条件分岐脱出フラグ(N桁目加算時50-N番地を利用)
- 41-51番地: 繰り返し用のカウンタ(N桁目加算時51-N番地を利用)
- 52-60番地: シフト用カウンタ(N桁目からN+1桁目へシフト時62-N番地を利用)**
- 61番地: 乗数
最後に考えるのは乗数の桁拡張です。
単純にメモリの領域を拡張します。また, 加算と同様に乗数の各桁に対する繰り返し処理を簡単にするために, 乗算ループ用カウンタを確保します。
- 61-70番地: 乗数
- 71番地: [k桁と1桁の乗算]の乗数各桁での繰り返し用カウンタ
桁が変わると処理位置が変わるからでは10桁分枠を取って相対位置考える必要があるんではないんですか？？ ということですが、今回は「k桁と1桁」の計算は毎回0-51番地の中の固定の位置で行われるため、乗数側が動いてくれないと相対位置が定まりません。つまり、シフトを利用して、現在処理する乗数の桁の数字が毎回70番地にいるようにする必要があり、逆に70番地に必ず乗数がいるので繰り返し用のカウンタは移動させなくていいというわけになります。
さて、乗数の右シフトのコードは先ほどのものを応用して作成すると下のようになります。
ここで、シフト用カウンタは加数シフト時の52-60番地をそのまま利用することにします。
//事前に70番地へ移動しておく
// 最下桁の破壊 (処理済のため)
[-]
// 60番地へ移動(右シフトでは処理桁が左へ移動していくため相対位置が変わらないようカウンタメモリは60番地から52番地へずれていく)
<<<<<<<<<<
// 9回繰り返す
+++++++++
[
//69 minus N番地へ移動してコピー処理
>>>>>>>>>[->+<]
// 戻る
<<<<<<<<<
// カウンタ更新&左移動
-[-<+>]<
]
これで準備が整いました。k桁と1桁の乗算のコードに外付けて各桁ごとに繰り返すためのシフト処理・カウンタ減算処理を加えると、最終的には10桁どうしの多倍長乗算は次のようなコードになります。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //71番地
++++++++++
//10回「k桁と1桁の乗算」を繰り返す
[
//乗数@70番地
<
//「k桁と1桁の乗算」
[
<<<<<<<<<<<<<<<<<<<++++++++++ //51番地
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
] // 終了後の(桁加算用)繰り返しカウンタ位置: 42番地
>>>>>>>>>>>>>>>>>>>>>>>>>>>>- // 乗数@70番地デクリメント
]
//被乗数最上桁@10番地
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
// 被乗数シフト
[-]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+++++++++
[<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[-<+>]>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>-[->+<]>]
// @60番地
//乗数最下桁@70番地
>>>>>>>>>>
// 乗数シフト
[-]
<<<<<<<<<<+++++++++
[>>>>>>>>>[->+<]<<<<<<<<<-[-<+>]<]
//@52番地
// カウンタ減算
>>>>>>>>>>>>>>>>>>-
]
コメントを外すとこのようになります。これで完成になります。お疲れ様でした。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
[
<
[
<<<<<<<<<<<<<<<<<<<++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>-
]
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[-]>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+++++++++[<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[-<+>]>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>-[->+<]>]
>>>>>>>>>>
[-]<<<<<<<<<<+++++++++[>>>>>>>>>[->+<]<<<<<<<<<-[-<+>]<]
>>>>>>>>>>>>>>>>>>-
]
まとめ
多倍長乗算が遂に完成しました。
あとは最後の砦、減算＋除算。それでは。