はじめに
筆算でやる方法、Newton-Rapson法があまりにも難しかったため脳筋回です。
前回のあらすじ！
減算による除算
除算とは、被除数が負にならない範囲で被除数を除数で何回減算できるかなので減算の繰り返しをすることで除算を行うことができます。
では実際にやっていきましょう。
減算の繰り返し
加算の繰り返しコードは#3よりこのようになっていました。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[
<++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
>>>>>>>>>>-
]
この時のメモリの内訳はこのようになっていました。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~29番地: 加数のコピー
- 30~40番地: キャリ
- 41~51番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:50-N番地, カウンタ領域: 51-N番地)
- 52番地: 加算全体の繰り返しカウンタ
この加算のコードでは、加数を復元する機能を付けることによって何度でも加算ができるようにするものでした。
減算では加数が「$B^D-1-N$」の部分になるため、#4同様に、これの頭に「$B^D-1-N$」計算部を取り付けることによって$B^D-1-N$を何度でも加算することができるようになります。
そのため、これに付け加えるべきは先ほどの計算コードと、ループ内で毎回キャリを1に設定する動作です。
また、繰り返しの終了条件は、最大桁の繰り上がりがないことなので、繰り返し回数を決めるのではなく、キャリの値が0かどうかを終了条件とします。
これを踏まえて減算の繰り返しコードを記述します。
メモリをこのように確保します。
- 0~9番地: 被減数
- 10~19番地: 減数の反転値
- 20~29番地: 減数の反転値のコピー
- 30~40番地: キャリ
- 30番地: 減算終了条件(キャリの最上桁)
- 41~51番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:50-N番地, カウンタ領域: 51-N番地)
- 52-61番地: 減数
するとコードはこのように書くことができます。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //カウンタ@51番地
//減数反転値の初期設定
++++++++++
[
//減数反転値N桁目へ移動(左32)
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
//255に設定
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
+++++++++++++++
//戻る(右32)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//カウンタ更新&左移動
-[-<+>]<
] //終了時@42番地
//カウンタ初期設定@51番地
>>>>>>>>>++++++++++
//減算処理
[
// 減数N桁目へ移動(右10)
>>>>>>>>>>
//減算 (距離42)
[- <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
- >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]
// カウンタへ移動(左10)
<<<<<<<<<<
//更新
-[-<+>]<
] //終了時@42番地
// 繰り返し減算
<<<<<<<<<<<<+ // キャリ最大桁@30番地 (初期値1としておくことでループを開始する)
[
[-] // キャリ最大桁を0に初期化
>>>>>>>>>>+ //キャリ最小桁の設定@40番地
>>>>>>>>>>>++++++++++ //@51番地
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
] //@42番地
<<<<<<<<<<<< //キャリ最大桁@30番地
]
多倍長除算
ここまできたらあとは減算回数をカウントするだけです。
減算回数のカウントをするために繰り返し加算用のメモリ領域を継ぎ足してこのようにメモリを取ります。
名称も除算用に変更します。
- 0~61番地: 減算用領域
- 0~9番地: 被除数
- 10~19番地: 除数の反転値
- 20~29番地: 除数の反転値のコピー
- 30~40番地: 減算用キャリ
- 30番地: 除算終了条件(キャリの最上桁)
- 41~51番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:50-N番地, カウンタ領域: 51-N番地)
- 52-61番地: 除数
- 62~71番地: 商
- 72~82番地: 商インクリメント用キャリ
- 83~93番地: 条件分岐脱出フラグ+繰り返し用のカウンタ(N桁目処理時 フラグ領域:92-N番地, カウンタ領域: 93-N番地)
インクリメントのコードは#2のおまけのコードから加数の加算コードを削除し、キャリの初期値を1に設定することでこのように書けます。
//事前に82番地へ移動しておく
+ //キャリ最下桁=1
>>>>>>>>>>>++++++++++ //@93番地
[
<<<<<<<<<<< //キャリN minus 1桁目 @82-N番地
[-<+<<<<<<<<<<+[>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
したがって、このコードを減算コードに埋め込んで完成になります。
ただし、除算終了時に被除数が負になっているため商が1大きい値になってしまいます。
そこで、初期値を$B^D-1$とすることで、帳尻合わせを行います。($B^D-1 \equiv -1 \mod B^D$より、$-1$を初期値としているのと同意味)$B^D-1$の設定は減数反転値の初期設定と同じなので説明は省略します。
完成コードは次のようになります。お疲れ様でした。
//商の初期設定
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> // @93番地
++++++++++
[
<<<<<<<<<<<<<<<<<<<<< //右21
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
+++++++++++++++
>>>>>>>>>>>>>>>>>>>>> //左21
-[-<+>]<
] //@84番地
//減数反転値の初期設定
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< //@51番地
++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
++++++++++++++++
+++++++++++++++
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
-[-<+>]<
]
//減数反転値計算
>>>>>>>>>++++++++++
[
>>>>>>>>>>
[- <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
- >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]
<<<<<<<<<<
-[-<+>]<
]
// 除算
<<<<<<<<<<<<+
[
[-]
>>>>>>>>>>+
// 減算
>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[
>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<+<<<<<<<<<<+
[>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
] //@42番地
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> //@82番地
// 商更新
+
>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<
[-<+<<<<<<<<<<+[>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
] //84番地
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< //キャリ最大桁@30番地
]
まとめ
脳筋は正義。
なおこちらの最大計算オーダーは$\mathcal{O}(B^N)$です。ありがとうございました(撃沈)。