読者です 読者をやめる 読者になる 読者になる

FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

brainfuckで数値を出力

d:id:tondol:20100630:1277839735の四則演算を利用してメモリ上の数値を10進数で出力してみました。例によって冗長なコードになっているので,実際のコードで利用(?)する場合は適宜最適化してやってください。

brainfuck

コメント中の「{@}」は下記の解説で登場する「ブロック」を表している気分です。「incr {@}」「decr {@}」などの表記は操作対象のブロックをひとつ右/左に移動するということを意味します。また,「{@0}」「{@1}」などの表記はブロック中の各区画を表している雰囲気です。

##################################################
### input
##################################################

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++

##################################################
### algorithm
##################################################

# {1} add !{0}
[->+<]

# while {@1} do
>[<

#   {@2} add 10
>>++++++++++<<

#   devide {@1:@2}
>
>>>+[<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]
<<[>[->+>+<<]>>[-<<+>>]<[[-]<->]<<-]+>[->+>+<<]>>[-<<+>>]<[[-]<<->>]<[[-]<<->>]<
[[-]<<+<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<[-<<<<<<->>>>>>]<<]<]<<[-]<[->+<
]>>[-<<+>>]<<
<

#   {@3:@4} add !{@0}
#   {@0}    add !{@4}
#   incr {@3}
[->>>+>+<<<<]
>>>>[-<<<<+>>>>]<<<<
>>>+<<<
#   {@4} add !{@1}
>[->>>+<<<]<
#   {@1} add !{@2}
>>[-<+>]<<

#   incr {@}
>>>

# end
>]<

# decr {@}
<<<

# while {@0} do
[
#   {@1} add 48
#   putchar {@1}
>++++++++++++++++++++++++++++++++++++++++++++++++<
>.<
#   decr {@}
<<<
# end
]

# {@1} add 48
# putchar {@1}
>++++++++++++++++++++++++++++++++++++++++++++++++<
>.<

C言語

ptr = 0; //メモリ上の0番地的な意味で
ptr[0] = 128;
ptr[1] = ptr[0];
ptr[0] = 0;

while (ptr[1]) {
  ptr[2] = 10;
  divide(&ptr[1], &ptr[2]); //ptr[1]÷ptr[2]の商と剰余をptr[1],ptr[2]にそれぞれ代入
  p[3] = p[0] + 1;
  p[4] = p[1];
  p[1] = p[2];
  ptr += 3;
}

ptr -= 3;

while (ptr[0]) {
  ptr[1] += 48;
  putchar(ptr[1]);
  ptr -= 3;
}

ptr[1] += 48;
putchar(ptr[1]);

解説

このプログラムの処理は大きく分けて2つの段階に分かれます。ひとつめはメモリを右方向へと移動(命令 '>' を実行)しながら,入力された(入力セクションでメモリの0番地に与えられた)値を各桁に分解し,メモリ上の各ブロックに格納する段階です。ふたつめはメモリを左方向へと移動(命令 '<' を実行)しながら,メモリ上の各ブロックに格納された各桁の値を出力する段階です。
説明中に登場した「ブロック」とは,3区画分のメモリをまとめて扱うための仮想的な概念です。ひとつのブロックはメモリ上の連続した3区画からなり,それぞれ左から「インデックス」「その桁の数値」「作業用スペース」として利用されます。ブロックは,メモリ上に連続して配置されており,たとえば,最初のブロックは0〜2番地,2つめのブロックは3番地〜5番地となります。
詳しくは解説しませんが,プログラムのひとつめの段階:分解フェーズでは,与えられた値を次々に10で割っていき,その余りを各ブロックに格納しています。与えられた値を10で割った結果が0になったら分解フェーズは終了です。分解フェーズが終了した段階で,メモリの内容は次のようになっているはずです。

[0][8][0]|[1][2][0]|[2][1][0]|[3][0][0]|...
                               ^ 分解フェーズ終了時点での操作対象ブロックはここ

メモリの内容を見ると,各ブロックの左から2番目の区画の値が各桁の数値に対応していることが分かります。
分解フェーズが終わったら,プログラムのふたつめの段階:出力フェーズに進みます。既に各桁の計算は終わっているので,操作対象のブロックを左に戻しながら,各ブロックの2番目の区画の値をアスキーコードに変換して(値に48を足して)出力するだけです。ここで,最も左のブロックまで進んだことを判定するために,予めブロックの1番目の区画に格納しておいたインデックスを利用しています。