Zenn
🧠

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

2024/12/01に公開
初心者向け
esolang
Brainfuck
tech

はじめに

※本記事は、2016/7/15にHatenaBlogに投稿した記事を移行したものです
今回でいよいよ最後になりました。トリとして、BCD演算を紹介したいと思います。

講座一覧

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

※上記以外も含め、各記事はBrainf**kの記事一覧から辿ることができます

実行環境

  • 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:フィボナッチ数列

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

  • 入力された数値 n ( 改行無し ) に対し、フィボナッチ数列の n 項目の値を出力する

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

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

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

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

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

そこで、BCD演算でフィボナッチ数列計算を実装したのが次のコードです。( ideoneでの実行例はこちら )

fibonacci
** set initial value and input n
** memory layout: nct_ab___ab____*
**  a:fib(0) b:fib(1) *:terminater minus 1
*-<<<<<b<<<<<b+<<<<
c,+[
 >t+++++++[-<c------->t]
 t<<n[->c++++++++++<n]
 n>c[-<n+>c]
c,+]

** memory layout:
*   Nn___ab___ab ~ __ab____*
*   N___AB____ab ~ __ab____*
*   N___ABdr__ab ~ __ab____*
*   N___AB___AB_ ~ _AB______
<n-[n
 * move n to N ( next n )
 n-[-<N+>n]
 * digit loop
 n->>>>>b+[b-
  * move b to A ( next a ) and add to a=B ( next b ) 
  b[-<aB+<A+>>b]
  * divmod by 10 ( add quotient to the right a )
  bd++++++++++
  <B[->d-[d>r+>_]>r_?[r+[-<d+>r]>>>a+<_]<<<<B]
  * clear d and move r to B
  >d[-]>r[-<<B+>>r]
 >>>>b ( slide )+]
 * judge if extend digit or not
 <<<<<<b[>>>>>]>>>>>-<+[-<+]n
<Nn]
* set terminater ( minus 1 ) to n
->+[->+]
* skip the highest digit ( 0 )
<<<<<<<<<<b
** output loop
** memory layout: *___ab___ab ~ _ab___abt
b+[b-
 >t++++++[-<b++++++++>t]<b.
<<<<<b+]

途中でセルの役割が切り替わりますので、“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 に移る状況を図示すると、次のようになります。

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

  • 繰り上がりに対処するため、変型版の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 で、桁の繰り上がり・拡張が発生する様子を図示すると次のようになります。

なお、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による実装です。
( ideoneでの実行例はこちら )

popcount
** input loop
** memory layout: mdt_dt_d~dt_*
*   m: the highest digit marker
*   d: each digits
*   *: terminater
m->d,+[
 >t+++++++[-<d------->t]
>>d,+ (slide)]
*-<+[-<+]m
** halving loop
** memory layout:
**   M_mn__n__n~__n__*p
**      ~Rh_rhn~__n__*p
**             ~Rh_*P_p
** M: new highest marker
** hr: result of d divmod 2
** R: left r
** pP: popcount ( previous and new )
m>n+[-
 ** set a new marker
 <<<M-
 ** n loop
 >>>n+[-
  ** borrow
  R<<<<[->>>>n++++++++++<<<<R]
  ** divmod by 2
  >>>>n[<r[-<h+>>>_]>n_?[n<h+>>>_]<<n-]
 >>>n+ (slide)]
 ** move p to P and add R ( the last R )
 >p[-<<P+>>p]<<<<<R[->>>P+<<<R]
 ** set a new terminater and return to the marker
 >>*-<+[-<+]M
 ** shrink if the highest digit is zero
 >[<<<]>>>h
hn+ (slide)]

** divmod loop **
>p[
 ** divmod by 10
 >++++++++++
 <[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
 >[-]>+
>]
** output loop **
<[-
 ** convert a number to a character code
 >++++++[-<++++++++>]
 <.
<<<]

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

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

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

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

まとめ

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

終わりに

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

Discussion