ズンドコキヨシ with Brainf**k

はじめに

みんな大好きズンドコキヨシ猫まっしぐら! …Perlで書いたんですが、BFでもまあ書いてみようかと。

注意点

ただし、BFにはそもそも乱数を扱う仕組みがありません。いえ、乱数生成アルゴリズムを自分で書くことはできますが、seedを受け取る ( 時刻情報等、seedに使える情報をOSから貰う ) 手段がありません。

ということで、ここはひとつ割り切って、seed はstdinからの入力文字列でこさえることにします。他の言語での実装との大きな違いですね。

まあ要するに、PRNGの実装を試してみるというのが大きな目的、ということでひとつ。

M系列

M系列というのは…。適当にググってください。bit-xorによる線型漸化式を適切に選べば、とっても長い周期のbit乱数が得られるPRNGです。

正直、線形合同法よりもBFでは実装が楽なので線形合同法はアルゴリズム集に載っているので、今回はM系列を実装することにしました。え? MT? はっはっはご冗談を。

M系列に使える漸化式は色々ありますが、最長周期$2^{28}-1$の隣接29項間漸化式、$r_n =r_{n-3}+r_{n-28}$を採用しました。( この足し算は$GF(2)$でのものであり、実装上はbit-xorです )

実装

ということで、以下がコードです。http://ideone.com/41y2ar にあるものと同じです。実行環境である ideone の bff に合わせて書いています。

詳しく説明するのは面倒くさいコメントに概要を載せているので、それで何とか ( 英語は即興なので多分デタラメです )。特徴としては、次の通りです。

• 出力文字列はutf-8のコード ( 1文字につき3byte ) を直に作っています。ただし、正の値で作るより、負の値の方が早いのでそうしています。( 例えば 0xe3 だったら -29 とか。od -td1でコードしらべたら負の値だったので面倒くさくてそのまま採用した、なんてことはありません )
• seedについては、入力文字列を7bitのbit-stringに変換して、それをつなげて使います。28bitだけ使うので、最後の4文字分が有効です。
• 乱数は、常に最新の28項を保持し、iteration毎に一番古い値を消して、新しい値を継ぎ足していくようにしています。
• 最初の方の乱数はseedの特徴が直に出やすいので、ループを空回りさせて捨てるようにしています。
• 単純に「最後の5個の乱数の値」で終了判定すると、まだ「ズンズンズンズンドコ」と出力し終わっていないにも関わらず、誤判定をおこしかねないので、ループカウンタの値で挙動を切り替えています。
  • ループカウンタが5以上の場合は、単に乱数を更新するだけ
  • ループカウンタが1～4の場合は、ズン/ドコも出力するが、終了判定は行わない
  • ループカウンタが0になった後は、「終了条件を満たさなければカウンタエクステンド」今風に言えば、「マリア、コンティニューだ」「サンキュ～マ・リ・ア!!」的な

zundoko.bf

* make seed from stdin *
,+[-
 * make 7bit bitstring
 [[->[-->+>>>+<<]>>[-<<]<<+<]+>>]
 <<[-<<]
>>>>>>>>>>>>>>>>,+]
* current memory state: (s_)*s_s_s*
* create a counter ( some initial random numbers should be discarded )
>++++++++++[->++++++++++<]
* M sequence generation loop
*  r(n)=r(n minus 3)xor r(n minus 28)
* memory layout:
*  (r_)*r_r_r__C
>[
 * slide and decrement the counter
 -[->>+<<]
 * move to the oldest random number ( 28 terms before )
 * ( making 2 markers to return )
 -<<<<<<++++[-<<++++++>>]-<<[-[-<<+>>]<<]
 * slide that to the next cell
 <[->+<]
 * move r(n minus 28) towards the top
 >>>+[-<<[->>+<<]>>>>+]
 * add r(n minus 3)
 <[-<+>>+<]>[-<+>]
 * move again
 +[-<<[->>+<<]>>>>+]
 * fix the bit ( change 2 to 0 )
 <<[-[->-<]>+<]
 * watch the counter
 *  if over 4: do nothing
 *  if 1 thru 4: only print "zun" or "doko"
 *  if 0: print "zun" or "doko" and judge wheter to extend the counter
 >>+>+>>+<
 * memory layout:
 *  (r_)*r_rpjCt
 *   p: print flag
 *   j: judge flag ( extension of the counter )
 *   t: temporary
 [-[-[-[-[++++<<->->>-
 ]>[-<    ++++<   ->>>]<
 ]>[-<    +++ <   ->>>]<
 ]>[-<    ++  <   ->>>]<
 ]>[-<    +   <   ->>>]<
 ]>[-                >]
 * print "zun" ( if the last random number is 0 ) or "doko" ( else )
 <<<<[
  ++++++[->>>>+++++>--------->-------->->--[---------<]<<<]+
  <[>->>> ->-.>+.>.<<.>-.>>>.+[,+<+]  ]
  >[->>>-> -.>.>>.<<<.>+.>>>.+[,+<+]> ]
 <<<<]
 * judge wheter to extend the counter
 *  calculate the sum of r(n minus 4) thru r(n minus 1) and ( 1 minus r(n) )
 *  extend the counter except the sum is 0 
 >[-
  >-<<<<<<<<+[-<<<[-<+>>+<]<[->+<]>>[->>+<<]>>>>+]<
  <+<[-<+>>-<]<[->+<]>>[[-]>>+<<]>
 ]
>]
* print "kiyoshi!"
+++++++[->>+++++++>------->->+>+++++<[-----------<]<]
>>-.>.>+.<<.>+.>>+.<<<.>.>-----.<<.>.>>.<<<.>-.>>----.>--.

終わりに

ついカッとなってやった。BFが組めればなんでも良かった。特に反省はしていない。