ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。BCD演算Brainf**kはじめに今回でいよいよ最後になりました。トリとして、BCD演算を紹介したいと思います。実行環境ideoneオンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。Brainf**kインタープリタあじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。終端」を「-1」と設定すると、bffと同じ挙動になります。ことで、要するに2進数なのだけど、10進数のように桁を分けて演算するというものです。筆算で計算するようなやり方を、Brainf**kのセル上で実現するイメージとなります。)前回足し算と数値の出力の問題を紹介したのですが、実はあのコードだと1つ困ったことがあります。それは、対象の数値が大きくなると、比例して処理時間が増大してしまうことです。せよ、対象の数値をループカウンタとしたループで処理しているからです。そこで、大きな数を処理したい場合にピッタリなのがこのBCD演算ということになります。桁の繰り上がり・桁数の調整が少し面倒ではありますが、複数桁からの集積、複数桁への展開の処理なく、ダイレクトに桁を扱え、処理が速いのが大きなメリットとなります。BCD演算の実例1:フィボナッチ数列まずは例として、フィボナッチ数列を計算するという問題です。なっているものとします。フィボナッチ数列の計算自体は、項をずらすように漸化式をループで回すことでできます。Rubyでのコードは次のようになります。bただ、フィボナッチ数列は指数的に値が大きくなっていきますので、1つのセルに値を保存するような方法だと、すぐに処理時間が爆発してしまいます。フィボナッチ数列計算の実装そこで、BCD演算でフィボナッチ数列計算を実装したのが次のコードです。layout”のコメントを幾つか入れています。特徴としては次の通りです。して、1の位同士、10の位同士、...と、同じ位の桁を隣り合わせにして配置するループの繰り返し毎に位置を1つずつずらしながら計算する。セルを設けて最上位の桁の方の終端とする。移る状況を図示すると、次のようになります。なくなったら桁を拡張する。桁の繰り上がり・拡張が発生する様子を図示すると次のようになります。しないのと同じ状況になります。BCD演算の実例2:popcount続いてはpopcountです。なっている桁の数のことを指します。問題としては次のようにします。繰り返すことになります。Rubyでのコードは次のようになります。計算が遅くなりますから、ここをBCD演算に替えます。popcountの実装それでは、Brainf**kによる実装です。時を例にとり、どのようにBCD演算を行っているかを次の図に示します。セルずつずらしていきます。用にカスタマイズし、必要な空きセルを節約しているからです。BCD演算とは、10進数の桁毎にセルに数値を割り当てる方式を指すのであって、その実装は問題ごとに変わってきます。BCD演算を繰り返しながらpopcountを更新していく様子は、次の図のようになります。なる毎に桁を縮小していき、最終的には終端に達してループが終了します。まとめ10進数の桁を各セルに割り当てることでBCD演算が行えるBCD演算は、大きな数を扱う時に、1セルでまとめて管理するよりも速度的に有利ただし、桁の繰り上がり・繰り下がり、桁の拡張・縮小の処理が必要になる各桁の処理用に、ある程度間を空けて桁を配置するただし配置をどのようにするかは問題毎に変わる終わりにこれまで、やや駆け足気味ながらBrainf**kの様々なコードのパターンを紹介してきましたが、いかがでしたでしょうか。Brainf**kを始める方、もっと色々なコードが書きたい方の一助となれば幸いです。いう観点からは様々な工夫の余地があろうかと思いますが、それは各読者の楽しみにとっておくことにします。最後まで読んで下さり、有難うございました。ネタがあれば、続きまたは番外編ということで書くかもしれません。2016、10日目の記事です。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。