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

Brainf**k講座(8) BCD演算

はじめに

今回でいよいよ最後になりました。トリとして、BCD演算を紹介したいと思います。

講座一覧

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

実行環境

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

今回の話題

BCD演算

BCDというのは Binary-Coded Decimal のことで、要するに2進数なのだけど、10進数のように桁を分けて演算するというものです。ちょうど、筆算で計算するようなやり方を、Brainf**kのセル上で実現するイメージとなります。( 本当に Binary-Coded なのかどうかは置いといて )

前回足し算と数値の出力の問題を紹介したのですが、実はあのコードだと1つ困ったことがあります。それは、対象の数値が大きくなると、比例して処理時間が増大してしまうことです。どうしてかというと、足し算にせよ divmod にせよ、対象の数値をループカウンタとしたループで処理しているからです。

そこで、大きな数を処理したい場合にピッタリなのがこのBCD演算ということになります。桁の繰り上がり・桁数の調整が少し面倒ではありますが、複数桁からの集積、複数桁への展開の処理なく、ダイレクトに桁を扱え、処理が速いのが大きなメリットとなります。

BCD演算の実例1:フィボナッチ数列

まずは例として、フィボナッチ数列を計算するという問題です。

フィボナッチ数列自体の説明は割愛します ( ご存じでない方はWikipediaの記事をご覧ください )。なお、初めの項は、1,1,2,… となっているものとします。

フィボナッチ数列の計算自体は、項をずらすように漸化式をループで回すことでできます。Rubyでのコードは次のようになります。

a,b=0,1
gets.to_i.times{
  a,b=b,a+b
}
puts b

ただ、フィボナッチ数列は指数的に値が大きくなっていきますので、1つのセルに値を保存するような方法だと、すぐに処理時間が爆発してしまいます。

フィボナッチ数列計算の実装

そこで、BCD演算でフィボナッチ数列計算を実装したのが次のコードです。

途中でセルの役割が切り替わりますので、“memory layout”のコメントを幾つか入れています。特徴としては次の通りです。

  • 一つ前の項を a、現在の項を b として、1の位同士、10の位同士、…と、同じ位の桁を隣り合わせにして配置する
  • ループの繰り返し毎に位置を1つずつずらしながら計算する。( 現在のn,a,bから新しいN,A,Bを設け、これを次のn,a,bとして使う )
  • 桁数が不定長なので、-1 のセルを設けて最上位の桁の方の終端とする。

計算の途中、$a=fib(3)=2, b=fib(4)=3$ から $a=fib(4)=3,b=fib(5)=5$ に移る状況を図示すると、次のようになります。

f:id:ange1:20160709075559p:plain

また、次の特徴もあります。

  • 繰り上がりに対処するため、変型版のdivmodにより、10での割り算を行う
    • 商q のセルを設けず、繰り上がり対象の右の a に直接商を加算する
    • a,bを5セルずつずらして配置しているのは、割り算用のセルの余裕を持たせるため
    • 余り r が真の B の値となる
  • 桁数の増加に対応するため、常に最上位の桁を 0 にしておき、0 でなくなったら桁を拡張する。
    • 足し算の性質上、1回の繰り返しで高々1桁しか増えないため、最上位の桁の 0 は1つで良い
    • この最上位の桁の 0 は、最後の出力の際スキップする

$a=fib(5)=5, b=fib(6)=8$ から $a=fib(6)=8,b=fib(7)=13$ で、桁の繰り上がり・拡張が発生する様子を図示すると次のようになります。

f:id:ange1:20160710072151p:plain

なお、B の値が10を超えなくても divmod は常に実行しています。ただ、a に加算する商が 0 で、余り r も元の B の値と等しくなるので、結果的に divmod しないのと同じ状況になります。

BCD演算の実例2:popcount

続いてはpopcountです。一般に ( かどうかは分かりませんが )、ある数を2進数表記した場合の 1 となっている桁の数のことを指します。問題としては次のようにします。

  • 入力 n ( 改行なし ) に対し、n の popcount の数値を出力する

どのように求めるかと言うと、2進数に展開するときと同様、divmod 2 を繰り返すことになります。その際の余りが 1 になるところが 1 になる桁に相当しますから、余りの合計を計算すればそれが popcount です。
Rubyでのコードは次のようになります。

n=gets.to_i
pc=0
while n>0
  pc+=n%2
  n/=2
end
puts pc

大きな数値の n に対してBrainf**kで実装する時、1セルで数値を管理すると divmod 2 の計算が遅くなりますから、ここをBCD演算に替えます。

popcountの実装

それでは、Brainf**kによる実装です。

n=893 の時を例にとり、どのようにBCD演算を行っているかを次の図に示します。

f:id:ange1:20160710093907p:plain

上のフィボナッチ数列のコードでは、2数を5セル毎に配置し、ループ実行毎に 1 セルずつずらしていきましたが、今回は n を3セル毎に配置し、ループ実行毎に 2 セルずつずらしていきます。
なぜこのような違いが出るかと言うと、扱う数が 2種類か 1種類かというのもありますが、divmod のコードを、divmod 2 用にカスタマイズし、必要な空きセルを節約しているからです。
あくまで BCD演算とは、10進数の桁毎にセルに数値を割り当てる方式を指すのであって、その実装は問題ごとに変わってきます。

なお、BCD演算を繰り返しながらpopcountを更新していく様子は、次の図のようになります。

f:id:ange1:20160710094022p:plain

divmod 2 の結果、最高位の桁が 0 になる毎に桁を縮小していき、最終的には終端に達してループが終了します。

まとめ

  • 10進数の桁を各セルに割り当てることでBCD演算が行える
  • BCD演算は、大きな数を扱う時に、1セルでまとめて管理するよりも速度的に有利
  • ただし、桁の繰り上がり・繰り下がり、桁の拡張・縮小の処理が必要になる
  • 各桁の処理用に、ある程度間を空けて桁を配置する
  • ただし配置をどのようにするかは問題毎に変わる

終わりに

これまで、やや駆け足気味ながらBrainf**kの様々なコードのパターンを紹介してきましたが、いかがでしたでしょうか。Brainf**kを始める方、もっと色々なコードが書きたい方の一助となれば幸いです。また、まだまだ golf という観点からは様々な工夫の余地があろうかと思いますが、それは各読者の楽しみにとっておくことにします。最後まで読んで下さり、有難うございました。もしまたネタがあれば、続きまたは番外編ということで書くかもしれません。