brainfuck 閑話：マルチバイト変数 設計編

概要

今回はマルチバイト変数（多バイト長整数）について書いていきます。 簡単に言うと、256 の数値を扱う方法です。
本当はもっと後に書く予定でしたが、知りたいという方がいたので前倒しで書きました。
今は閑話としてカテゴライズして、後でもう一度まとめようと思います。

目次

マルチバイト変数の概要

brainfuck ではマルチバイト変数は自分で作るしかありません。
しかし、これといったセオリーがあるものではなく、

• 命令の実行時間はどうか
• 命令のコード長はどうか
• 自身が扱いやすいかどうか

なとどいった重要要素が多くあるので、これといったセオリーがあるわけではありません。
なので、今回は私が作成したマルチバイト変数を紹介しつつ、設計方法の説明をしていきたいと思います。
もちろん、私が紹介したコードをそのまま使用してもらっても構いませんし、 私のコードを改変して使用してもらっても構いません。

データ格納方法の検討

マルチバイト変数と一括りに行ってしまっても、その設計方法は様々です。設計の上で検討するべき項目を以下に示します。

• 何進数を採用するか
• 固定長か可変長か
• 1 桁に対して何 byte を割り当てるか
• 各変数の前後に何 byte の余裕を持たせるか
• 負数をどうするか

それぞれ詳しい説明をしていきます。

何進数を採用するか

数字がいくつになった場合に桁上がりが発生するか、です。
進数が小さければ小さいほど、使用メモリが多くなり、大きれば大きいほど、様々な演算処理が重くなる印象です。 以下は実装を検討しても良いであろう進数を書きます。

• 1 進数
• 8 進数
• 10 進数
• 16 進数
• 256 進数

1 進数は桁上がりなどは簡単ですが、メモリ量が膨大なためおすすめはしません。
256 進数はメモリ的には最良ですが、桁上がりなどがめんどくさそうなのと、計算の実行速度が遅くなりそうです。
8 進数、16 進数は bit 演算と相性が良さそうですが、入出力がめんどくさいという欠点があります。
10 進数は、bit 演算と相性が悪いという欠点がありますが、入出力が簡単です。
以上より、私は 10 進数を採用しています。
余裕がああれば、10進数と、8 または 16 真数の両方作ってもいいかもしれませんね。

固定長か可変長か

固定長は計算が楽になり、可変長はメモリ使用量が少なくなります。
私は、固定長で実装しています。

1 桁に対して何 byte を割り当てるか

1 桁に対して複数 byte を用意するのは不思議かもしれませんが、理由はあります。
まずは、そのメモリが、桁として有効かどうかを示す必要があることです。
具体的には、0 が格納されているメモリが、「変数の末端（変数の領域外）なのか、0 という数値が格納されているのか」 という問題を解決するために、桁に使用されているメモリであることを明示する必要があります。
桁数をハードコーディングしてもいいですが、桁数ごとに加算などの桁数を変更しないといけないという欠点があります。
また各桁に対して空きメモリを用意することで、各桁に対する演算を行うためのワーキングメモリとして役立つことも多いです。
基本的には 3 byte 用意すれば十分なように思います。
ここまでの話を否定するようですが、私は 1 桁 1 byte を採用しています。
上記の問題の具体的な解決方法は後述します。

各変数の前後に何 byte の余裕を持たせるか

変数間の空きは変数の端を検出するだけでなく、二項演算の処理のワーキングメモリにすることもできます。
変数の端を検出するためには、1 桁当たりの byte 数以上の空きを用意する必要があります。
私は、3 byte を採用しています。

負数をどうするか

負数をどうするかもいくつか方法があります。

• 補数表現
• 絶対値表現
• 実装しない

補数表現はそのままで、実質符号なし整数と同じようにアンダーフローを実装して、一定以上なら負数とみなす方法です。
絶対値表現は、符号と絶対値による表現です。
実装しないは、動作未定義もしくは、負数は全て 0 にする方法です。
実際は、未定義にするのが楽ですが、汎用性を考えると実装したいです。
絶対値表現もいいのですが、条件分岐がめんどくさくなるため、 私は補数表現を採用しました。
また、補数表現も、1 の補数と 2 の歩数がありますが、2 の補数を採用しています。
ちなみに、簡単のため、最上位が 0 なら正それ以外なら負として扱っています。
負数の方が数字を多く表現できることになりますが、基本的に数桁余裕を持ってコードを書くため、0 か 9 以外を取らないことになります。

設計方針のまとめ

• 10 進数
• 可変長
• 1 桁に対して 1 byte を割り当て
• 各変数の前後に3 byte の余裕
• 負数を補数表現で実装

1 桁 1 byte の実現方法

先ほど説明したとおり、「変数の末端（変数の領域外）なのか、0 という数値が格納されているのか」を判別する必要があります。それを 1 byte で表現するために、 各桁の値に 1 足した値を採用しています。
例えば、固定長 6 桁で 129 を表現する場合

{0} {0} {0} {1} {1} {1} {2} {3} {10} {0} {0} {0}

となります。
まぁ、今では 2 byte 用意しても良かったのとは思っています。

実装する演算

マルチバイト変数の設計方針がある程度固まったらあとは様々な演算等を実装していくだけです。
個人的に思う優先度ごとにわけて記述します。

必要演算

ほぼ必須となる演算や処理です。 * 入力 * 出力 * インクリメント * デクリメント

高優先度演算

必須演算で代用することもできますが、計算量の関係で実装しておいたほうがいい演算が主です。

• 加算
• 減算
• 比較
• 非零判定
• 正負判定

あると嬉しい演算

高優先度演算で実装できるが実装しておいたほうが計算量が削減できるものと、時々必要になる演算が主です。

• 比較
• スワップ
• 絶対値
• 符号反転
• シングルバイト変数との積算
• シングルバイト変数での剰余算

無くても良い

必要になる機会はありますが、実装がめんどくさい演算です。

• マルチバイト変数同士の積算
• マルチバイト変数同士の剰余算

次

実際の実装は別記事にまとめようと思います。

brainfuck 記事一覧

brainfuck 入門：リンクまとめ - 三流プログラマの戯言