Zenn
🧠

Brainfuckで多倍長整数 (1)

2024/12/12に公開
AtCoder
esolang
Brainfuck
tech

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

はじめに

ここでは、筆者が AtCoder で brainfuck を書くに際して躓いた、多倍長整数の実装について紹介します。そのため処理系や実装方針は AtCoder に合わせて考えています。
この記事が多倍長整数の実装に悩んでる方の一助となれば幸いです。

中級者向けの記事なので、brainfuck の基本的な言語仕様についての解説は割愛します。
必要な方は wiki などの他のサイトを参考にしてください (こちらの講座がおすすめです)。

また、筆者は brainfuck を学んで日が浅いこともあり、理解の浅い点や冗長なコードを書いている可能性が非常に高いです。改善点がありましたらご教示ください。

実装方針

  • 10進数
    AtCoderでは10進数での入出力を多用します。
    基数変換をその都度するのは面倒なので、10進数で格納します。
  • 固定長
    可変長は魅力的ですが、固定長の方が実装が楽で、TLE 時に実行時間を縮めるのも比較的容易だと思います。
    可変長を実装するのが筆者には困難であるという問題が一番大きいです。
  • 1桁 1byte
    各桁に1を足した数を格納することで、桁の数値としての0 と セルの初期値の0 を区別します。
    今回は採用しませんが1桁に対して 2byte 以上を割り当てる方法だと、多倍長整数の桁として格納されていることを示したり、演算中で様々な処理を行うときの実装を楽にしたりできて便利です。
  • 2の補数
    負の数を表す方法として、一定以上の数を負数と考える補数表現を用います。
    1の補数と2の補数がありますが、ここでは2の補数を採用します。
    符号と絶対値を両方持つ方法もありますが、符号による条件分岐が必要になって少々面倒です。

こちらは実装方針を考える上で大変参考にさせて頂いたサイトです。
https://unidentifiedexe.hatenablog.com/entry/2019/10/24/145345

基本演算

数値入出力やインクリメント・デクリメントといった、基本的な演算の実装例を解説とともに紹介します。どれも多倍長整数を扱う上で必須級な演算になります。

数値入力

ここでは EOF, LF, SP のいずれかが入力されるまで非負整数を読み込む場合を考えます。
以下は実装例です。

数値入力 (非負整数)
01: >>>+>+>+>+>+ >+>+>+>+>+   # 桁数指定 (ここでは10桁)
02: >>,+[                     # 最初の位を受け取ってループ開始
03: ----- ----- -[            # LFならbreak
04: <+++++[->----<]>--[       # SPならbreak
05: [-<+>]+++++[-<--->]       # '0'を1に変換 (合計47を引く)
06: <[<]>->[[-<+>]>]          # 先頭の位を消して各桁を1マス移動
07: ,+<]]>]                   # 入力を受け取ってEOF以外ならループ (3行目に戻る)
08: <<<[<]                    # 位置合わせ

お気持ち

要は新しい桁を多倍長整数の末尾に取り込むごとに、各桁をずらして不要な先頭のゼロを消去するということです。

表を用いた説明

↓ 例: "12345" が読み込まれた状態で '6'(=0x36) を読み取ったとき

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

読み取った数値を末尾に加えて、全体を左にずらしてるのがわかると思います。

詳細な解説

雑に分割して解説します

block 1
01: >>>+>+>+>+>+ >+>+>+>+>+

左に3マス空けた状態で、1を連続してセットします。
この1の数が多倍長整数の桁数になります。

block 2
02: >>,+[
03: ----- ----- -[
04: <+++++[->----<]>--[

AtCoderの実行環境では EOF は-1であるため、,+[ とすることで EOF の場合はループに入らないよう分岐します。
2行目で1を足したので、11を引くことで LF の場合にbreakします。
同様に SP の場合にもbreakします。

block 3
05: [-<+>]+++++[-<--->]
06: <[<]>->[[-<+>]>]

合計47を引くことでascii codeから数字に1足された値に変換します ('0' のascii codeは48)。
6行目では現在の多倍長整数の末尾に入力された数字(+1)を取り入れ、<[<]>- で先頭の0(+1)を取り除きます。そのために、5行目のうちに左へ1マス移動しておきます。
また、実行後の多倍長整数の位置が合うように [[-<+>]>] で各桁を左へ1マス移動させます。

block 4
07: ,+<]]>]

,+ で入力を受け取りますが、その後 <]] によって明らかに値が0のマスへ移動して分岐を閉じます。こうすることで、受け取った入力を EOF かどうかの分岐に持っていくことができ、かつ LF, SP で分岐を超えた場合は>]の先は明らかに0のマスとなりループを抜け出します。

block 5
08: <<<[<]

入力が EOF で終了した場合と、LF, SP で終了した場合で現在地が1マス異なるため、多倍長整数の桁を利用して位置を合わせます。ここで <<<[<] は <<[>] でも構いません。

ポイント

予め入力を受け取る位置を多倍長整数の末尾の2マス右にしておき、入力が数字であることが保証された段階で左に移動させます。これは7行目の分岐を閉じた <]] 後の >] で、LF や SP の分岐を飛んできた場合と辻褄を合わせるためです。

数値出力

ここでは非負整数を非破壊的に出力する場合を考えます。
以下は実装例です。

非破壊数値出力 (非負整数)
01: -                         # 目印設置
02: >>>[-[+<<]>]              # 先頭の0は出力しない
03: >[                        # 先頭の桁からループ開始
04: -[-<+>]+[+++++<+>]<---.   # 一桁出力 (1マス左へ移動)
05: ++++>+[+++++<->]>]        # 元の数値に戻して次の桁へ (4行目に戻る)
06: <+<[>-]>[                 # もし多倍長整数が0なら
07: [+++++<+>]<---.[-]>]      # '0'を出力してbreak
08: <<[[->+<]<]               # 各桁を1マス右に移動
09: >+[<+]>->-                # 先頭の0を復帰 (目印を使用)

お気持ち

Leading zeros を一旦消去して、残りの桁を出力したら、Leading zeros を元に戻します。
ここで問題なのが 0 ですが、これは2マス左に桁が存在するかで分岐して 0 を出力させます。

表を用いた説明 1

出力が 1234 となる場合

↓ Leading zeros は出力しないので、目印 -1(=0xFF)を置いて先頭からゼロを消していきます。

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

↓ ゼロを消し終わったら残った桁を出力します (随時左に移動させることで非破壊を実現します)。

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

あとは多倍長整数を元の形に戻すだけです (ここで目印 -1 が桁数を保存します)。

表を用いた説明 2

出力が 0 となる場合

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

0 の場合でも同様、元に戻れました。

数値と ascii code を変換する際の補足説明

+[+++++>+<]>--- について

これは右のマスに48を加算するコードです ('0' の ascii code は48)。
セルの数値が8bit、即ち255を + すると0になることを利用しています。
こうすることで文字数を短縮できますが、単純に +++++ +++[->+++++ +<] としても良いです。

ポイント

出力が 0 の場合の条件分岐 <+<[>-]>[ が少々テクニカルです。2マス左に数が存在するかで分岐しますが、ここでは非破壊 if を用いています。0 の場合は現在地が異なることも計算に入れて調整します。

インクリメント・デクリメント

地味によく使う演算ですが、桁上がりの実装が面倒なので頑張って工夫します。

インクリメント

以下は実装例です。

インクリメント
01: >>>[>]+[               # 末尾の1マス右からループ開始
02: +++++ ++++<[->->+<<]   # 桁を2マス右に移動する & 10から引く
03: +>[[-]<->]<]           # その桁が9(10)ならループ (2行目に戻る)
04: >>[+[-<<+>>]]          # 見た中で一番上位の桁を1足して元の位置に
05: >[[[-]<<+>>]>]         # それ以降の桁は0(1)で置き換え

お気持ち

09999(1AAAA) のように 9(A) が続く場合は 10000(21111) としたい訳なので、末尾から 9(A) が連続する部分を見ます。9(A) でない桁を見つけたら、その桁を1足して残りはゼロを連ねます。
ネックになるのが 9999999999(AAAAAAAAAA) を 0000000000(1111111111) とする点ですが、具体的な解決方法については「お気持ち」から逸れるので下で解説します。

上記の問題の解決方法について

ループの開始位置を桁から1マスずれた位置にすることで解決します。
これによって、次の桁が存在しないときにも1回だけループが呼び出されます。
この時、4行目で1足して移動させる対象となる一番上位の桁は 0 となります。
ここで、4行目を >>+[-<<+>>]とせずに >>[+[-<<+>>]]と括弧で括るのがポイントです。
括弧で括ったことによって、0 の場合のみ括弧内が実行されないため、桁数を維持したまま 0000000000(1111111111) という結果を得ることができます。

デクリメント

以下は実装例です。

デクリメント
01: >>>[>]+[                   # 末尾の1マス右からループ開始
02: <[->->+<<]                 # 桁を2マス右に移動する & 1から引く
03: +>[[+]<->]<]               # その桁が0(1)ならループ (2行目に戻る)
04: >>[-[-<<+>>]]              # 見た中で一番上位の桁を1引いて元の位置に
05: >[[[-]<<+++++ +++++>>]>]   # それ以降は9(A)で置き換え

お気持ち

インクリメントと大差ありません。10000(21111) を 09999(1AAAA) にする訳です。
同様に末尾から 0(1) が連続する部分を見て、0(1) でない桁を見つけたらその桁を1引いて、残りは 9(A) を連ねます。

まとめ

  • 数値入力
    1桁読むごとに、多倍長整数の末尾に付け加えてずらす。
  • 数値出力
    Leading zeros を消去して出力、Leading zeros 復帰。
  • インクリメント・デクリメント
    末尾の 9(A), 0(1) の塊を置き換える。
数値入力 (非負整数)
>>>+>+>+>+>+ >+>+>+>+>+ // number of digits
>>,+[----- ----- -[<+++++[->----<]>--[
[-<+>]+++++[-<--->]<[<]>->[[-<+>]>],+<]]>]<<<[<]
非破壊数値出力 (非負整数)
->>>[-[+<<]>]>[-[-<+>]+[+++++<+>]<---.++++>+[+++++<->]>]
<+<[>-]>[[+++++<+>]<---.[-]>]<<[[->+<]<]>+[<+]>->-
インクリメント
>>>[>]+[+++++ ++++<[->->+<<]+>[[-]<->]<]>>[+[-<<+>>]]>[[[-]<<+>>]>]
デクリメント
>>>[>]+[<[->->+<<]+>[[+]<->]<]>>[-[-<<+>>]]>[[[-]<<+++++ +++++>>]>]

なんか解いてみる

せっかく基本的な演算が実装できたので、AtCoder 上で簡単な問題を解いてみましょう。
今回はこれらの基本演算が使えれば実装できるであろう問題を2問選出しました。

1問目 - 植木算

https://atcoder.jp/contests/abc007/tasks/abc007_1
数値入力、デクリメント、数値出力。すべて既に習得していますね。

実装例 + 解説
ABC007-A 植木算
数値入力
>>>+>+>+>+>+
>>,[----- -----[-[-<+>]+++++ +[-<----- ->]<[<]>->[[-<+>]>],<]>]<<[>]
デクリメント
+[<[->->+<<]+>[[+]<->]<]>>[-[-<<+>>]]>[[[-]<<+++++ +++++>>]>]
破壊的数値出力
<<<[<]>[-[+<<]>]<+>>[<+[+++++>+<]>----.[-]>]<<[[+++++>+<]>---.<]+++++ +++++.

提出結果

ちょっとした解説

紹介したものから適宜変更しています。

  1. 先ずは数値入力ですが、LF が読まれるまで入力を受け取るようにしました。
    EOF, SP でも入力を終えるプログラムの場合かなりの字数を使いますが、この問題では LF が入力されることが保証されているので字数を抑えることができます。
  2. 数値入力の最後の位置調節を <<<[<] から <<[>] に変更しました。
    これは次のデクリメントをする際に、現在地が多倍長整数の右隣である方が都合が良いからです。
    これに伴ってデクリメントの最初の >>>[>] を省略できました。
  3. 数値出力を破壊的にしました。
    この問題では出力後に元の数値が残っている必要がないので、破壊的にして字数を抑えます。

2問目 - ペア

https://atcoder.jp/contests/abc034/tasks/abc034_b
こちらは先ほどの問題より少し難易度が上がっています。
偶奇判定の結果によってインクリメント・デクリメントを使い分けなければなりませんが、この記事では偶奇判定の実装方法を紹介していません。自力で実装してみると良いでしょう。

実装例 + 解説
ABC034-B ペア
数値入力
>>>+>+>+>+>+ >+>+>+>+>+
>>,[----- -----[-[-<+>]+++++ +[-<----- ->]<[<]>->[[-<+>]>],<]>]<<[>]
偶奇判定
-<[->>+>+<<<[->>+>-]>+[-<+]-<]>+>[-<<+>>]+>[-<- // 偶数
デクリメント
<+[<[->->+<<]+>[[+]<->]<]>>[-[-<<+>>]]>[[[-]<<+++++ +++++>>]>]]<[- // 奇数
インクリメント
<+[+++++ ++++<[->->+<<]+>[[-]<->]<]>>[+[-<<+>>]]>[[[-]<<+>>]>]<]
破壊的数値出力 (正数)
<<[<]>[-[+<<]>]>[<+[+++++>+<]>----.[-]>]+++++ +++++.

提出結果

ちょっとした解説

紹介したものから適宜変更しています。

  1. 先ずは数値入力ですが、LF が読まれるまで入力を受け取るようにしました。
    EOF, SP でも入力を終えるプログラムの場合かなりの字数を使いますが、この問題では LF が入力されることが保証されているので字数を抑えることができます。
  2. 数値入力の最後の位置調節を <<<[<] から <<[>] に変更しました。
    これは次の偶奇判定をする際に、現在地が多倍長整数の右隣である方が都合が良いからです。
  3. 偶奇判定を実装しました。
    偶奇判定は末尾の桁を見れば十分です。見る桁の左が空いてないので右隣に -1 を置いて、その右にコピーを作りつつ、更に右のマスに偶奇判定の結果を格納しました。偶奇判定のやり方に関してはもっと良い実装がたくさんあると思われます。スマートな実装を考えてみるのも面白いかもしれません。
  4. 数値出力を破壊的にしました。
    この問題では出力後に元の数値が残っている必要がないので、破壊的にして字数を抑えます。
  5. 0 を出力する場合を考慮しない設計にしました。
    この問題では 0 という答えはあり得ないので、よりシンプルで短いコードになります。

色んな問題に挑戦しよう

高難易度な問題を解くには加減算がないと厳しいところが多々ありますが、工夫すれば今回見てきた基本的な演算のみでも解ける問題がある、ということは理解していただけたかと思います。
AtCoder や他の競プロサイト等で、brainfuck で様々な実装をして楽しみましょう。

筆者よりも遥かに熟練のプロ brainfucker の方々もたくさんいるので、そういった方々の実装を眺めたり競ったりするのも楽しいと思います。

おわりに

以上、今回は brainfuck での多倍長整数の実装方針と、基本的な演算の実装例をご紹介しました。
次回は多倍長整数同士の加減算や比較、乗算についてご紹介できたらと思っています。

人生で初めて記事を書いたこともあって拙い箇所が多数あったかと思いますが、ここまで読んでいただき誠にありがとうございました。

Discussion