2006年07月05日

Re: BF2JS opimizing compiler

BFにはまっておられる奥さんに。
(brainfu.k - BF2JS opimizing compiler - 404 Blog Not Found)

 弾さん、ありがとうございます。 String.prototype.replace でコンパイラを実装しているのが美しいと思います。

 自分でも触りたくなったので、単純な Dead code elimination と、いくつかの Peephole Optimization を追加してみました。特にゼロクリアと加算処理の最適化は効果が大きかったようで、手元のパソコンでは、素数計算が2秒以内で完了するようになりました。

 代入処理全体を置換したり、あるいは、ループ内でメモリの値をローカル変数に割りつけたりといった、さらなる最適化の余地は残っていますが、おいしいところは片付けられたかな、という感じです。

続きを読む "Re: BF2JS opimizing compiler"

投稿者 kazuho : 2006年07月05日 13:16 | トラックバック (0) このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

2006年06月30日

Brainf*ck で動的リスト

 Brainf*ck では、メモリアドレスを動的に指定することはできません。しかし、そのような制約があるからといって、リストを使用したプログラムを書ことができないわけではありません。

 Brainf*ck の場合、ちょうど C の文字列のように、要素列の前後にターミネータを置くことで動的リスト構造を表現することができます。でもそれだけじゃおもしろくないので、考えをもう一歩進めて、動的リストをイテレートできないか考えてみました。

 というわけで、以下が電車の中で書いたコードです。任意の長さの動的リストをイテレートして、その総和を表示します。

続きを読む "Brainf*ck で動的リスト"

投稿者 kazuho : 2006年06月30日 11:06 | トラックバック (0) このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

2006年06月28日

brainf*ck でマジメに素数探索

 「キミならどう書く 2.0 - ROUND 1 - 」の〆切は過ぎていますが、逃避力を発揮して brainf*ck で書いてみました。

 竹迫さんのものとは違い、brainf*ck で素数探索を行っています。でも brute force なアルゴリズムなので遅いです (笑)

続きを読む "brainf*ck でマジメに素数探索"

投稿者 kazuho : 2006年06月28日 17:12 | コメント (2) | トラックバック (1) このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

brainf*ck で計算機

 竹迫さんのbpencodeを皮切りに、brainf*ck ネタが盛り上がっています。Brainf*ck の基本的な処理については英語版 Wikipedia: Brainf*ck に書いてあるのですが、 if ~ then ~ else ~ endif については、なぜか記載がありませんでした。

 どうやって実現すればいいのかな、と考えていたのですが、

# p[0]=cond, p[1]=0 の場合
>+<[[-]>-< then-clause ]>[-< else-clause >]<

でいいことに気づきました。というわけで、実証を兼ねて計算機を作ってみることに。

続きを読む "brainf*ck で計算機"

投稿者 kazuho : 2006年06月28日 11:52 | トラックバック (0) このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク