HN 日本語サマリー

← 一覧へ戻る
プログラミング

BSD Makeエクストラバガンザ:bmakeでのマンデルブロ集合

BSD Make extravaganza: Mandelbrot Set In bmake (github.com)

22 pointsby signa113 コメント

要約

この記事は、BSDのmakeビルドシステムのみを使用してマンデルブロ集合のレンダラーを実装したプロジェクトについて説明しています。著者は、makeの計算能力の限界を探求し、バイナリを一切呼び出さずに、加算、減算、乗算、除算といった基本的な算術演算をmakeの機能で実現しました。このレンダラーは非常に非効率的ですが、makeの汎用性を示すユニークなデモンストレーションとなっています。

全文翻訳

BSD Makeエクストラボガンザ。

[画像: バナー。最初のミニブロのレンダリング] 最初のミニブロ、レンダリングに12時間。1000x250 z=32, it=64, re=-1.777 im=0

FreeBSD portsシステムを使い、そのmakeファイル群とmake(1)のマニュアルページを大量に読んだ結果、この言語が計算普遍的であることを実感しました。この発見の後、視覚的なデモンストレーションを作成し、makeの限界を試したい衝動を抑えることができませんでした。

マンデルブロ集合レンダラーは、以前からそれを本来の目的外の場所に押し込む経験があったため、自然に思いつきました。これは、基本的な要素を多く必要とする、十分に包括的なプログラムです。また、デモンストレーション目的にも役立つ、ある程度計算負荷の高いものでもあります。

こうして、このプロジェクトが誕生しました。純粋なBSD makeで書かれ、いかなるバイナリも呼び出さない、完全なマンデルブロ集合レンダラーです。

[画像: マンデルブロ集合のレンダリング、中程度のイテレーション回数] マンデルブロ集合、レンダリングに36時間18分。1000x500 z=2, it=64, re=-1.4 im=0

このプログラムの使い方:

このリポジトリをクローンします:

git clone https://github.com/b-aaz/bmake-extravaganza
cd bmake-extravaganza

プリセットされたデフォルト値に基づいた低解像度画像のレンダリング:

make > output.ppm

出力された画像は、PPM形式をサポートする画像ビューアで表示できます。

ffmpegの内部ビューアffplayを使用する場合:

ffplay output.ppm

または、PNGのようなより一般的な形式に変換することもできます:

ffmpeg -i output.ppm output.png

異なる変数を使用してレンダリングする場合:(これは、ズームレベル1の200x100画像をレンダリングします)

make w=200 h=100 z=1 > output.ppm

注意!これは恐ろしく非効率的なレンダラーです。中解像度の画像でも、入力変数とシステム仕様によっては、レンダリングに必要な時間は簡単に1週間以上の100%連続CPU使用率に跳ね上がります。

ヒント: 計算される定数が「短い」入力変数を使用してみてください。定数に多くの桁(小数部または整数部)が含まれる場合(周期数など)、加算器、減算器、乗算器などの関数は余分に動作する必要があります。そのため、より高解像度の画像でも、定数が「長い」低解像度の画像よりも「逆説的に」レンダリング時間が短くなることがあります。

利用可能なフラグの詳細については、以下を参照してください:

make help

よくある質問と回答:

1. ストライプは何ですか?

それは幸運な事故です。修正しようとはしていません。それが作るユニークなパターンが好きです。おそらく、不審な「浮動小数点」実装の多くのエッジケースの1つが原因でしょう…。[画像: 低イテレーション回数でレンダリングされたマンデルブロ集合、ストライプが表示されている] マンデルブロ集合、レンダリングに14時間。1000x500 z=2, it=10, re=-1.4 im=0

2. どうやって編集するのですか?

VimでBSD makeの適切なシンタックスハイライトがなかったため、自分で書く必要がありました。このプロジェクトに非常に役立ちました:bmake.vim

3. 全体の仕組みのTL;DRは?

要するに、加算、減算、乗算の3つの基本的な演算はすべて、単純な10進数の小学校アルゴリズム(長い加算、単純な繰り上がり加算/減算)に基づいています。これらは単純なルックアップテーブルを使用し、入力数値の各桁に繰り返し適用します。一方、除算は、まず分母の逆数をニュートン・ラフソン法で見つけ、次に分子をそれに掛けることによって行われます。(「高速除算」と呼ばれることもあります)他のすべては、これらのプリミティブ(とループ「関数」)の上に構築されています。このプロセス中にパフォーマンスにも配慮しましたが、改善の余地はまだたくさんあると思います。

3.1. なぜ2の補数(または10の補数)を使わないのですか?

これらの特殊な状況では、多くの一般的なパターンが同じ結果をもたらしません。すべての桁を反復する必要がある繰り返し反転の累積コストと、オーバーフローメカニズムに依存する必要があるコスト(これは各数値でさらに多くの反復を必要とします)は、すべてを遅くするでしょう。

3.2. なぜ一部の領域にコメントがないのですか?

これらのファイルをすべての操作で繰り返し.includeしているため、空行1つ1つが重要なので、パフォーマンスを向上させるために、本当にホットなコードセクションではコメントを削除する必要がありました。

3. BSD-makeで書かれた他のものへの計画は?

それは読者への演習です。このプロジェクトからインスピレーションを得て、バイナリ演算、あるいは単純なISAを実装するというクレイジーなアイデアもあります。可能性は無限大です。


[画像: FreeBSD搭載] [画像: vimで編集] [画像: bmake最高!バッジ(私が作成(bmakeでレンダリング!:b))]