Brainf**k講座(7) divmodアルゴリズムと数値出力

Brainf**k

はじめに

前回で一通り、処理の制御を終わりましたBrainf**k講座、今回からは応用として、良く使う典型的な処理を紹介していきたいと思います。

講座一覧

  1. Hello, BF!
    導入およびシンプルなループによる数値生成
  2. 数値入力と簡単なループ
    ,による入力と数値解釈、簡単なループの実例
  3. スライド型ループ
    ループ継続の判断を行うセルの位置をずらしていくループ
  4. 条件分岐
    if文、if-else文相当の処理
  5. 条件分岐の多段化
    switch文相当の処理
  6. 非破壊的条件分岐
    条件変数を壊さない条件分岐
  7. divmodアルゴリズムと数値出力
    除算・剰余算のアルゴリズムと、それを利用した不定長の数値出力

実行環境

  • ideone
    オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。
  • Brainf**kインタープリタ
    あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。
    ※オプションで「バッファの型」を「4バイト符号付き整数」、「標準入力の終端」を「-1」と設定すると、bffと同じ挙動になります。

今回の話題

divmodアルゴリズム

divmodとは、ご存じの通り除算・剰余算をまとめて行うものです。

実は、割り切れることが予め分かっているのであれば、除算は次のように簡単に書けます。

a[---->b+<]

これは、a÷4の値をbに加算する例です。aをループ変数として、4減らす間にbを1増やすことで、結果的に割り算を行っています。

しかしながら、これでは余りが出ることに対応できません。なぜなら、ループ終了条件が 0 である以上、ピッタリ割り切れないと、a がマイナスの値に突入していつまでも抜け出せないからです。

そこで、divmodアルゴリズムの出番となります

divmodアルゴリズムの実装

divmodアルゴリズムですが、cleverな実装が知られており、“Brainfuck algorithms” に紹介されています。

2通りありますが、一方は被除数のバックアップを同時に取るだけの違いなので割愛しますと、次のようなコードになります。

** memory layout: ndrqXY
n[n->d-[>r+>>X]>Yr?[r+[-<d+>]>q+>>Y]Y<<<<<n]

最初に用意しておくのは、次の数です。

  • 被除数 n
  • 除数 d

処理が完了した時、各セルは次のようになります。

  • n → 0
  • d → d-n%d
  • r → n%d
  • q → n/d

このコードでは、dの評価のところで前回説明した非同期的な条件分岐を使っており、if か else かで途中セルの位置がずれています。また、X,Yはセルの位置調整用のブランクセルです。

処理内容をRubyで書いてみると、次のようになります。

while n>0
  n-=1
  d-=1
  if d>0
    r+=1
  else
    d=r+1
    r=0
    q+=1
  end
end

各セルの動きを図示すると次のようになります。

f:id:ange1:20160708173051p:plain

つまり、前回取り上げた問題“FizzBuzz - Fizzだけ”のように、全体のループのカウンタ n とは別に d をカウンタとして使うことで、周期的に q を増やしていくということを行っています。r は d のバックアップでもあり、divmod終了時に余りを保持するものでもあります。

数値出力

さて。divmodアルゴリズム自体は良く使うものなのですが、特に何が嬉しいかというと、10進数での数値出力ができるようになる、というところです。

これまでは、セルの数値が1桁の場合に限り、48を足して文字コードに変換することができました。しかし、これでは10以上の数値に対応できません。

そこで、10 での divmod を繰り返すことで、10進数表記での各桁を作っていくということを考えます。

数値出力の実装

10進数で何桁になるかは事前に分かりませんから、被除数が 0 より大きいというループ持続条件のもと、スライド型のループで各桁を作っていきます。

** memory layout: ndrq__
n[
 ** set 10 to d as a divide number
 >d++++++++++<n
 ** divmod
 n[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
 ** clear d
 >d[-]
>>qn]

このコードの動作は次の図のようになります。

f:id:ange1:20160708175051p:plain

divmodでの商q が、次のループでの被除数 n にスライドし、10進数の各桁がその時々の r に残っていくことになります。n と q とは 3セル離れているので、できる桁も 3セル置きになります。なお、divmodが終わった時の d ( n-n%d ) は不要なので、ループの最後でクリアしています。

divmodと数値出力の実例

それでは、divmodと数値出力の実例として次のような足し算問題を考えます。

  • 1行毎に数値が2行分入力されるとき、その合計を出力する

これに対するBrainf**kのコードは次のようになります。

最初は、カウンター 2 でのスライド型ループで入力の解釈、続いて加算を行った後、divmodの繰り返しで10進数の桁を作っていきます。

なお、29行目で r をインクリメントしているのは、10進数の終端としてブランクセルを使っているためです。余りが 0 になった時に、終端のブランクセルと区別がつかないとまずいので、一時的にインクリメントしておき、出力の時にその分デクリメントして使います。

まとめ

  • 非同期な条件分岐を使った divmod アルゴリズムがある
  • divmod を繰り返し使うことで 10進数展開ができる

終わりに

divmod アルゴリズムは、本当に良く使うので、これで対応できる問題の幅がかなり広がるものと思います。次回でBCD演算を取り上げ、最後にしようと思います。