BFではじめる円周率計算入門 #2 -加算の簡略化-

## 前回のあらすじ！
小学2年生ハードモード
[BFではじめる円周率計算入門 #1 -1桁どうしの乗算-](https://qiita.com/nekoMIMI_CatEye/items/47090145eac08895bb2e?utm_campaign=post_article&utm_medium=twitter&utm_source=twitter_share)

## 筆算と加算
乗算は筆算ベースでやろうと思います。
筆算をするにあたって、10桁と1桁の乗算を10回、桁をずらしながら行う必要があるわけですが、10桁と1桁の乗算は「10桁どうしの加算」によって行われるため、そのコードが長いととんでもないコード長になります。
そこで、あの加算コードを短くしたいというわけですが、どうやって短くするか。乗算の時に使った「繰り返し」を応用すると短くなりそうです。
それではやっていきましょう。

## 絶対位置から相対位置へ
10桁どうしの加算のコードはこのようになっていました。

```brainfuck
>>>>>>>>>>>>>>>>>>>
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->]<<<<<<<<<<<]
<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>]<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>]<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>]<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>]<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>]<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>]<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>]<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>]<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>]<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>]<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>]<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>]<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>]<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>]<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>]<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>]<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
```

しかし、計算する桁が移動していっているのに対して、条件分岐脱出用のメモリ位置が変化していないため、全く同じコードの繰り返しではまずそうです。
そこで、条件分岐脱出用メモリ、そして新たに追加する繰り返し用のカウンタの2つが計算する桁に対して相対的に不変の位置になるようにメモリの取り方を変えてみます。
上のコードはこのようなメモリの取り方をしていました。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~29番地: キャリ
- 30番地: (条件分岐脱出用)
キャリ減算後に条件分岐脱出用のメモリへ、また条件分岐脱出後に、計算している桁の加数(またはキャリ)の番地へ移動するときの相対距離を変えないようにするにはどうすればいいでしょうか。
条件分岐脱出用のメモリを10個分取っておいて、「この桁ではこのメモリが条件分岐脱出用として機能する」というように対応付ければいい訳です。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~29番地: キャリ
- 30~39番地: (条件分岐脱出用)
こうすることで、一番距離が遠い場合にすべて合わせることができるため、コードの中身をそろえることができます。
変更後のコードはこのようになります。
```brainfuck
>>>>>>>>>>>>>>>>>>>
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>]<<<<<<<<<]
<<<<<<<<<<<<
```

## 疑似的なキャリの確保
現在、0桁目の加算にはキャリがありません。
しかし、0桁目の加算だけループから外す、となると非常に厄介なので、0桁目の計算に「キャリ0を足す」という動作を付けることによって、1桁目以降と同じ動作に無理やりしていきます。
キャリを1つ余分に取ります。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~30番地: キャリ
- 31~40番地: (条件分岐脱出用)
するとコードは次のようになります。

```brainfuck
>>>>>>>>>>>>>>>>>>>
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
```
これで下のコードの繰り返しにすることができました。

```brainfuck
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
<<<<<<<<<<<<
```
## 繰り返し用のメモリ確保
さて、あとはこれを10回繰り返す操作を入れればいいことになります。
しかし、繰り返し用のカウンタは相対位置が変わらないようにしなければいけないため、工夫する必要があります。
桁の計算位置はポインタの前方に一つずつずれていくため、繰り返しのたびにカウンタを1減らすと同時にポインタの位置を(相対位置を固定にするために)1つ手前に寄せればよいことになります。
したがって、このようにメモリを取ることで繰り返しを実現します
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~30番地: キャリ
- 31~40番地: (条件分岐脱出用)
- 41~50番地: 繰り返し用のカウンタ(ただし50番地の初期値を10として、繰り返しのたびに41番地へ向けて位置をずらす)
これにより、最終的には10桁どうしの加算コードは次のようになります。
```brainfuck
// 50番地へ移動
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
// 50番地の値を10にする(10桁の加算)
++++++++++
// 10回繰り返す
[
// 左へ31ポインタ移動(=加数のN桁目)
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
// 加数N桁目を被加数N桁目に加算 (Nplus1桁目へキャリ)
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]
// キャリN桁目に移動
>>>>>>>>>>>
// キャリN桁目を被加数N桁目に加算 (Nplus1桁目へキャリ)
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]
// 右へ20ポインタ移動(=カウンタの位置)
>>>>>>>>>>>>>>>>>>>>
// カウンタを1減算
-
// カウンタの格納位置を1左へずらす
[-<+>]<
]
```
コメントを外すとこのようになります。
```brainfuck
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>>>>>>>>>>
-[-<+>]<
]
```

## おまけ 繰り返し用メモリと条件分岐フラグの統合
繰り返し用メモリを10個分別で取ると、全体で50個になりとても使用領域が広くなってしまいます。
そこで、条件分岐フラグを11個とり、条件分岐フラグの右側にいつも繰り返し用カウンタがいる状態を作ります。
11個の領域についてカウンタ以外はすべて0になっているため、条件分岐は正常に動作します。
- 0~9番地: 被加数
- 10~19番地: 加数
- 20~30番地: キャリ
- 31~41番地: 条件分岐脱出フラグ+ 繰り返し用のカウンタ(N桁目処理時 フラグ領域:40-N番地, カウンタ領域: 41-N番地)

これにより、カウンタまでの移動距離も短くなるのでコードも次のように短くなります(ポインタ移動が減っただけ)

```brainfuck
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++
[
<<<<<<<<<<<<<<<<<<<<<<
[->>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<]>>>>>>>>>>>
[-<+<<<<<<<<<<<<<<<<<<<<+[>>>>>>>>>>>>>>>>>>>>->>>>>>>>>>>]<<<<<<<<<<]>>>>>>>>>>>
-[-<+>]<
]
```

## まとめ
10桁の加算をここまで短くすることができました。
これで筆算のコードを現実的な長さで書く準備が整いました。それでは。