Brainfuckで多倍長整数 (2)

この記事は 朝活部 Advent Calender 2024 18日目の記事です。

はじめに

前回に引き続き、brainfuck による多倍長整数の実装例についてご紹介します。
今回は多倍長整数同士の加減算や比較の実装例を見ていきましょう。

前回の内容 (実装方針, 数値入出力, インクリメント, デクリメント) は既知として話を進めます。内容的にもより複雑になると思われるので、まだ理解されていない方は先に前回の記事を読むことを推奨します。

加減算と比較

桁ごとに加減算を計算してから、全体の桁上がりをするという順序で加減算を実装します。
極論インクリメント・デクリメントを繰り返せば同等のことができますが、計算量が膨大になるので今回は不採用とします。

加算

ここでは2つの多倍長整数 $α$, $β$ が3マス間隔で並んでいて、左の多倍長整数 $α$ に右の $β$ を加算する場合を考えます。ただし、2つの多倍長整数の桁数は等しいものとします。
以下は実装例です。せっかくなので非破壊的な実装をご紹介します。

加算 (非破壊)

01: >>>[>]>>>[                                              # βの先頭からループ開始
02: -<<+[<]<[<]>[-<+>]                                      # αの足される桁を用意
03: >[>]>[>]>[-<<+[<]<[<]<+>>[>]>[>]>]                      # 一桁足しつつコピー
04: >]                                                      # 次の桁 (2行目へ)
05: <<<[[->>+<<]<]                                          # βを2マス右へ
06: <<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[   # 桁が10(B)以上なら
07: >[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]                   # 桁上がり
08: <]                                                      # 次の桁

お気持ち

先ずは足し合わせる部分について。
2つの多倍長整数の桁数が等しいことが保証されているので、$β$ の桁をあるだけ足していきます。
また、そのついでにコピーを作ることで非破壊を実現します。

次に桁上がりについてですが、$α$ の末尾の桁から始めて 10(B) 以上かという判定をしつつ、元の数値を保存しておきます。10(B) 以上でかつ上の桁が存在するなら (最上位の桁でなければ)、1つ桁上がりして更に 10(B) 以上か確認します。10(B) 未満であれば次の桁を見ていきます。

表を用いた説明

↓ 例: $α = 297(3A8)$ に $β = 143(254)$ を加算します。

番地	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E
1行目末尾	0	0	0	3	A	8	0	0	0	*2	5	4	0	0	0
4行目末尾	0	0	4	E	B	0	0	2	5	4	0	0	*0	0	0
5行目末尾	0	0	4	E	B	0	*0	0	0	2	5	4	0	0	0

↓ 次に、$α$ の桁上がりを実行します。

番地	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E
7行目末尾	0	0	4	F	1	*0	0	0	0	2	5	4	0	0	0
〃(2)	0	0	4	F	*0	1	0	0	0	2	5	4	0	0	0
〃(3)	0	0	5	5	*0	1	0	0	0	2	5	4	0	0	0
〃(4)	0	0	5	*0	5	1	0	0	0	2	5	4	0	0	0
〃(5)	0	0	*0	5	5	1	0	0	0	2	5	4	0	0	0

徐々に桁上がりしているのが理解していただけたでしょうか。

というわけで、計算結果の 440(551) が $α$ に格納されました。

詳細な解説

雑に分割して解説します

block 1

01: >>>[>]>>>[
02: -<<+[<]<[<]>[-<+>]
03: >[>]>[>]>[-<<+[<]<[<]<+>>[>]>[>]>]
04: >]

$β$ の最上位の桁からループを開始し、下位の桁へとずらして行きます。

今回のループで加算される $α$ の桁を分離し、分離した桁に $β$ の数値を加算していきます。このとき、-<<+ によって「お気持ち」で説明したコピーが2マス左に作られます。

また、今まで作られてきたコピーが左に連なっていることを利用して、<<[<]<[<]> で $α$ の先頭の桁に飛び、[>]>[>]> で今見ている $β$ の桁へ飛びます。

あとは >] で $β$ の次の桁に移動してから分岐を閉じます。

多倍長整数の桁は1を足した状態で格納されているため、$α$ に加算するときは1を引いてからループを開始します。このとき、同時に作ったコピーには <<+ で1を足した状態にします。

---

block 2

05: <<<[[->>+<<]<]

$β$ をコピーする際にずれた分を戻します。

---

block 3

06: <<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[

$α$ の末尾から桁上がりを判定していきます。

10(B) 以上か 10(B) 未満かで分岐しますが、今見ている桁の数値を保存しておくために1マス右へ最大10まで移動します。

(厳密にはこのコードは 0 ~ A とそれ以外で分岐します。)

---

block 4

07: >[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]
08: <]

10(B) 以上の場合には今見ている桁から10を引き、上位の桁に (存在するなら) 1を足します。
10(B) 未満の場合は6行目によって数値が既に右に移動しているため、次の桁を見ます。

ここでは、>[-] で最大の10まで溜まった右のマスをクリアすることで10を引きます。
[->+<]<[+>]>[<]>[-<+>] とすることで、上位の桁が存在しない場合にも桁数を維持します。上位の桁に相当する位置が 0 の場合に桁を追加しないために [+>] としますが、これによって現在地がずれます。これを揃えるために、見ていた数値を利用して >[<]>[-<+>] とします。

減算

2つの多倍長整数 $α$, $β$ が3マス間隔で並んでいて、左の多倍長整数 $α$ から右の $β$ を引く場合を想定します。ここでも $α$ と $β$ の桁数は等しいものとします。
以下は実装例です。

減算 (非破壊)

01: >>>[>]>>>[                                               # βの先頭からループ開始
02: -<<+[<]<[<]+++++ ++++>[-<+>]                             # αの引かれる桁を用意
03: >[>]>[>]>[-<<+[<]<[<]<->>[>]>[>]>]                       # 一桁引きつつコピー
04: >]                                                       # 次の桁 (2行目へ)
05: <<<[[->>+<<]<]                                           # βを2マス右へ
06: <<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[   # 桁が10(B)以上なら
07: >[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]                    # 桁上がり
08: <]                                                       # 次の桁

お気持ち

前回の実装方針でも述べた通り負数は2の補数で表現するので、右の多倍長整数 $β$ の2の補数を $α$ に加算すれば良いです。基本的な構造や、桁上がりの実装は加算と共通です。

表を用いた説明

↓ 例: $α = 47(158)$ から $β = 195(2A6)$ を減算します。

番地	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E
1行目先頭	0	0	0	1	5	8	0	0	0	*2	A	6	0	0	0
4行目末尾	0	0	9	5	C	0	0	2	A	6	0	0	*0	0	0
5行目末尾	0	0	9	5	C	0	*0	0	0	2	A	6	0	0	0

↓ 次に、$α$ の桁上がりを実行します。

番地	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E
7行目末尾	0	0	9	6	3	*0	0	0	0	2	A	6	0	0	0
〃(2)	0	0	9	6	*0	3	0	0	0	2	A	6	0	0	0
〃(3)	0	0	9	*0	6	3	0	0	0	2	A	6	0	0	0
〃(4)	0	0	*0	9	6	3	0	0	0	2	A	6	0	0	0

というわけで、計算結果の -148(963) が $α$ に格納されました。

• 負数の表現に2の補数を用いているため、-148 は3桁の多倍長整数において 852(963) と表される点に注意してください。
• 今回は表の幅の関係で3桁にしていますが、普段このような演算を扱うときは桁数に余裕を持たせてください。例えば、5桁で -148 を表現すると 99852(AA963) となります。

ポイント

各桁を計算する際 9(A) からその桁の値を引いた数を足しますが、これだけでは1の補数を足していることになります。ここで6行目行頭 <<+ によって $α$ の末尾の位に1を足し、1の補数から2の補数へ変換しています。6行目から桁上がりが行われるので、前回行ったようなインクリメントの操作は必要ありません。

比較

2つの桁数の等しい多倍長整数 $α$, $β$ が3マス間隔で並んでいて、$α ≧ β$ かを判定する場合を想定します。今回は先に紹介した加減算を用いて、特に何も考えずに実装します。
上位から1桁ずつ大小を見ていくのも手ですが、負数が絡むのが厄介です。
以下は実装例です。

比較 (非破壊)

減算
>>>[>]>>>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<+[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
正負判定
<+>>>[-<+>[-<+>[-<+>[-<+>[-<+>[[-<+>]<<<->>>]]]]]]<[->+<]
加算
>>>[>]>>>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<+[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]

お気持ち

$α - β$ の正負を判定して、元の状態に戻します。おわり。

一応解説

雑に分割して解説します

block 1

減算
>>>[>]>>>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<+[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]

$α - β$ を計算します。

---

block 2

正負判定
<+>>>[-<+>[-<+>[-<+>[-<+>[-<+>[[-<+>]<<<->>>]]]]]]<[->+<]

$α - β$ の結果が非負なら 1 を、負なら 0 を0番地 (スタート地点) に格納します。
このとき、最上位の桁が 5(6) 以上なら負数とみなします。

---

block 3

加算
>>>[>]>>>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<+[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]

$α$ の値を元に戻すために、$β$ を加算します。
このとき正負判定の結果が邪魔になる気もしますが、問題ありません。

まとめ

• 加算
  各桁足し合わせて桁上がり
• 減算
  2の補数を足して桁上がり
• 比較
  加減算を用いて正負判定

加算 (非破壊)

>>>[>]>>>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<+[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]

減算 (非破壊)

>>>[>]>>>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<+[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]

比較 (非破壊)

>>>[>]>>>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<+[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
<+>>>[-<+>[-<+>[-<+>[-<+>[-<+>[[-<+>]<<<->>>]]]]]]<[->+<]
>>>[>]>>>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<+[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]

なんか解いてみる

数値の入出力に加えて、加減算ができると解ける問題の幅が一気に広がります。
ということで、AtCoder 上で簡単な問題を解いてみましょう。
今回はこれまで紹介した演算が使えれば解けるであろう問題を4問選出してみました。

1問目 - Two Coins

https://atcoder.jp/contests/abc091/tasks/abc091_a
数値入力、加算、比較。これまで紹介してきた演算ばかりです。

解説 + 実装例

テキトー解説

1. 入力 A, B を受け取って和を取る
2. 入力 C を受け取って和 S と比較
3. 和 S が C 以上のとき "Yes", 未満のとき "No" を出力

---

実装例

ABC091-A Two Coins

memory layout: __fA(S)___B(C)___

read num: A
>>>+>+>+>+>+
>>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<[>]
read num: B
>>>+>+>+>+>+
>>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<<[<]
add B: A
>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
read num: C
>>[>]>>>[>]>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<<[<]
compare(S ge C): f
>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
>+>[-[-[-[-[-[[-]<->]]]]]]
print(f ? "Yes" : "No")
+<[+++++ +++++[->+++++ +++<<+++++ ++++<+++++ +++++>>]>.<<++.<+++++.>[-]]
>[+++++ +++++[-<+++++ ++<+++++ +++++>>]<+.<+.<]

提出結果

余談ですが、筆者は普段こんな風にコメントを入れながら brainfuck を書いてます。

2問目 - Theater

https://atcoder.jp/contests/abc073/tasks/abc073_b
加減算の良い練習になるでしょう。

解説 + 実装例

テキトー解説

1. N は必要ないので改行まで飛ばす
2. L を読み取って 0 でなければ (EOF でないなら) ループ
3. L を Sum から引く
4. R を読み取って Sum に足す
5. Sum をインクリメントする
6. 2に戻る
7. Sum を出力

---

実装例

ABC073-B Theater

memory layout: ___S___L(R)___

skip until LF
+[,----- -----]
set 0: S
>>>+>+>+>+>+ >+
read num: L
>>>>+>+>+>+>+ >+
>>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<<[<]
while: L
>[-[+[<]<]+>]>[[>]>]<<[<]<[-
subtract L: S
>>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
read num: R
>>[>]>>>[>]>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<<[<]
add R: S
>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
increment: S
>>[>]+[+++++ ++++<[->->+<<]+>[[-]<->]<]>>[+[-<<+>>]]>[[[-]<<+>>]>]
read num: L
>[>]>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<<[<]
end while: L
>[-[+[<]<]+>]>[[>]>]<<[<]<]
write num: S
<<[<]>[-[+<<]>]>[<+[+++++>+<]>----.[-]>]

提出結果

3問目 - Can you buy them all?

https://atcoder.jp/contests/abc209/tasks/abc209_b
加算と比較に加えて、前回の問題でも行った偶奇判定の実装です。
(工夫すれば偶奇判定せずとも解けますが。)

解説 + 実装例

テキトー解説

1. N は必要ないので空白まで飛ばす
2. X を読み取る
3. A を読み取って 0 でなければ (EOF でないなら) ループ
4. flag が立っているなら A をデクリメント (最初は false)
5. flag を反転
6. A を Sum に足す
7. 3行目に戻る
8. X が Sum 以上なら "Yes", 未満なら "No" を出力

---

実装例

ABC209-B Canyou buy them all?

memory layout: __aX___S___A___f

skip until space
+[,>+++++ +++[-<---->]<]
read num: X
>>>+>+>+>+>+
>>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<[>]
set 0: S
>>>+>+>+>+>+
read num: A
>>>>+>+>+>+>+
>>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<[>]
while: A
<[-[+[>]>]+<]<[[<]<]>>[>]>[-
if(f) decrement: A
>+>[-<-<<+[<[->->+<<]+>[[+]<->]<]>>[-[-<<+>>]]>[[[-]<<+++++ +++++>>]>]>]
set !f: f
<[->+<]
add A: S
<<<[<]>[-<<+[<]<[<]>[-<+>]>[>]>[>]>[-<<[<]<[<]<+>>[>]>[>]>]>]
<<<[[->>+<<]<]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
read num: A
>>[>]>>>[>]>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<[>]
end while: A
<[-[+[>]>]+<]<[[<]<]>>[>]>]
compare(X ge S): a
<<[<]<<<[<]>[-<<+[<]<[<]+++++ ++++>[-<+>]>[>]>[>]>[-<<[<]<[<]<->>[>]>[>]>]>]
<<<[[->>+<<]<]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<[->+<]<[+>]>[<]>[-<+>]]]]]]]]]]]<]
>+>[-[-[-[-[-[[-]<->]]]]]]
print(a ? "Yes" : "No")
+<[+++++ +++++[->+++++ +++<<+++++ ++++<+++++ +++++>>]>.<<++.<+++++.>[-]]
>[+++++ +++++[-<+++++ ++<+++++ +++++>>]<+.<+.<]

提出結果

4問目 - Sum of Three Integers

https://atcoder.jp/contests/abc051/tasks/abc051_b
普通の問題としても、他と比べて少し難易度が高いですね。
大変ですが、前回と今回で紹介した内容をフル活用することで解けます。

解説 + 実装例

テキトー解説

頑張って $O(K)$ で解きます。

---

ABC051-B Sum of Three Integers

memory layout: ___X___K___S_f_A___

read num: X
>>+>+>+>+>+
>>,+[----- ----- -[<+++++[->----<]>--[[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<[>]
copy X: K
<[[->+>>>>> >>>+<<<<< <<<<]<]
increment: X
>>[>]+[+++++ ++++<[->->+<<]+>[[-]<->]<]>>[+[-<<+>>]]>[[[-]<<+>>]>]
read num: S
>[>]>>>+>+>+>+>+
>>,+[----- ----- -[<+++++[->----<]>--[[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<[>]
set 0: A
>>>+>+>+>+>+ >+>+>+>+>+[<]
while: X
<<<[<]<<<[<]<+[-
decrement: X
<+[<[->->+<<]+>[[+]<->]<]>>[-[-<<+>>]]>[[[-]<<+++++ +++++>>]>]
if(S lt 0): *__S
>[>]>->>-[+<]+<[+>-]+<+[->-
set 0: X & end if: *__S
<<<[<]<<<[[-]+<]>[>]>>>[>]>]
else: *_S
>[-
subtract K: S
>[+++++ +++++>]<[<]<<<[[->+>>>>> >>-<<<<< <<<]<]>>[>]>>[[-<+>]>]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
[->+<]<[+>]>[<]>----- -----[-<+>]]]]]]]]]]]<]
set (S lt 0): f
+>>-[+<]+<[>->[>]>+<<[<]]<-
add K: S
<<<<<[-<+>[-<+>>>>> >>>+<<<<< <<]>]>>[[-<+>]>]
<<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<<[+>>]<[<]>>[>]]]]]]]]]]]<]
if(S lt K): f
>>[>]+>[-<-
add S & increment: A
<[->+<[->+>>>>> >>>>> >>+<<<<< <<<<< <<<]<]>>[[-<+>]>]>>[[-<+>]>]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<<[+>>]<[<]>>[>]]]]]]]]]]]<]
end if: f
]
else: S*_f
<[-
subtract 2K & decrement: S
<[+++++ +++++ +++++ +++++ +++++ ++++<]
<<<[[->+>>>>> >>--<<<<< <<<]<]>>[[-<+>]>]>>[[-<+>]>]
<<++[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<<[+>>]<[<]>>[>]]]]]]]]]]]<]
if(S lt 0): *__S
->>-[+<]+<[+>-]<+[-
subtract S: A
>>[>]>>>[+++++ +++++>]<[<]<<<[[->+>>>>> >>>>> >>-<<<<< <<<<< <<<]<]
>>[[-<+>]>]+++++[[>]>[-<+>]<[<]>-]>[----- ----->]>[[-<+>]>]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<<[+>>]<[<]>>[>]]]]]]]]]]]<]
end if: *__S
<<[<]<]
add 2K & increment: S
<<[->+<[->+>>>>> >>++<<<<< <<<]<]>>[[-<+>]>]>>[[-<+>]>]
<<+[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[
>[-]<<[+>>]<[<]>>[>]]]]]]]]]]]<]
end else: S*_f
>>[>]]
end else: *_S
<[<]<]
decrement: S
>>[>]+[<[->->+<<]+>[[+]<->]<]>>[-[-<<+>>]]>[[[-]<<+++++ +++++>>]>]
end while: X
<<<[<]<<<[<]<<<[-[+[>]>]+<]<[[<]<]>>[>]>]
write num: A
>>[>]>>>[>]>>>[-[+<<]>]>[<+[+++++>+<]>----.[-]>]+++++ +++++.

提出結果

おわりに

以上、今回は brainfuck による多倍長整数同士の加減算と比較について実装例をご紹介しました。
次回は乗算について書きたいですね。(非負整数に限らない場合の数値入出力など、まだ紹介していない何かしらについて書くかもしれません)

いずれにせよ、ここまで読んでいただいて本当にありがとうございました。