問題タブ [mandelbrot]

私は現在、非常に巨大な（65536x65536ピクセル以上の）マンデルブロ画像を生成するプログラムを作成しています。それらを正当化するスペクトルとカラーリングスキームを考案したいと思います。ウィキペディアで紹介されたマンデルブロ画像は、特にシーケンスのすべてのズームレベルでパレットがどのように変化したままであるかを示す優れた例のようです。ただし、パレットを回転させているのか、それとも他のトリックを実行してこれを実現しているのかはわかりません。

私はマンデルブロ集合の滑らかな彩色アルゴリズムに精通しているので、バンディングを回避できますが、このアルゴリズムからの出力値に色を割り当てる方法が必要です。

私が生成している画像はピラミッド型であるため（たとえば、それぞれが前の画像の半分のサイズの一連の画像）、次の画像の間でパレットが変更されている限り、ある種の回転パレットを使用できます。ズームレベルはそれほど明白ではありません。

マンデルブロ集合の画像を生成するための Python ファイルを作成しました。元の数学コードは私のものではないので、理解できません.250倍速くなるように大幅に変更しただけです(スレッドルール!)。

とにかく、コードの数学部分を変更して特定のビットをレンダリングする方法を考えていました。数学の部分は次のとおりです。

サイズの定義:

セットの特定のセクションをレンダリングするには、何を変更する必要がありますか?

ステータス:これまでのところ、最良の回答のプログラムは元のプログラムの 33% の時間で実行されています! しかし、おそらくそれを最適化する他の方法がまだあるでしょう。

Lua は現在、最速のスクリプト言語ですが、C/C++ に対するいくつかのベンチマークでは、Lua のスコアが非常に低くなっています。

それらの 1 つは、マンデルブロ テスト (マンデルブロ セット ポータブル ビットマップ ファイル N=16,000 を生成) で、1:109 (マルチ コア) または 1:28 (シングル コア) という恐ろしいスコアを付けます。

速度のデルタが非常に大きいため、これは最適化の良い候補です。また、Mike Pall が誰であるかを知っている人は、これ以上最適化することはできないと考えるかもしれませんが、それは明らかに間違っています。最適化を行ったことがある人なら誰でも、常に改善できることを知っています。それに加えて、いくつかの微調整で追加のパフォーマンスを得ることができたので、それが可能であることを知っています:)

では、これをどのように最適化できますか (もちろん、他の最適化と同様に、より高速であることを確認するために実装を測定する必要があります)。また、Lua の C コアを変更したり、LuaJit を使用したりすることは許可されていません。それは、Lua の弱点の 1 つを最適化する方法を見つけることです。

編集:チャレンジをより楽しくするために、これに賞金をかけます。

私はRubyで迅速/効率的なマンデルブロ実装を作成しようとしています。ずっと前に、それをスピードアップする1つの方法は、浮動小数点数の代わりに固定小数点整数を使用することでした。

そこで、乗算または二乗**オペランドを使用して、浮動小数点と整数の累乗を二乗と比較して、次のベンチマークを作成しました。

これにより、次の出力が生成されます。

これは、Fixnumの乗算が浮動小数点のほぼ2倍遅いことを明確に示しています。

2つの質問があります：

• 誰かがこれを説明できますか？私が想像できる理由は、Fixnumの乗算は、Bignumに変換する必要があるかどうかを内部でチェックするために遅いためです。
• 第二に、ルビーの簡単な整数乗算よりもありますか？

私はいくつかの異なる言語でのマンデルブロー集合の実装に取り​​組んできました。私は C++、C#、Java、および Python で動作する実装を持っていますが、Common Lisp の実装には、私には理解できないバグがいくつかあります。セットを生成しますが、パイプラインのどこかでセットが歪んでしまいます。ファイル I/O CLO が問題ではないことをテストし、ほぼ確実に知っています。可能性は低いですが、かなり徹底的にテストしました。

これらの実装の目的は、相互にベンチマークすることであることに注意してください。そのため、コードの実装を可能な限り類似させて、比較できるようにしています。

マンデルブロー集合 (ここでは Python 実装によって生成されます):

「マンデルブロー集合（Pythonで生成）」

しかし、私の Common Lisp プログラムはこれを生成します:

「Common Lisp版の歪んだマンデルブロー集合」

このバグは、Clisp と SBCL の両方で同じです。

コード：

一般的な Lisp:

それに最も近いのは Python です。

必要に応じて、C++、C#、または Java コードも投稿できます。

ありがとう！

編集: Edmund の応答のおかげで、私はバグを見つけました-移植時に亀裂をすり抜けたものです。変更されたコード:

コードはあまり LISP 風ではありませんが (これは言葉ですか?)、動作します。投稿/コメント/回答してくれたすべての人に感謝します:)

Open Gl と NVidia が提供する CGFX SDK を使用して、単純なマンデルブロ エクスプローラーを作成することができました。うまく機能しますが、現在はフロートベースであるため、「深さ」はあまりありません。最小の複素数から最大の複素数までの距離が小さくなると、精度が失われ、結果の画像が「ピクセル化」されます。

残念ながら、CGFX は倍精度をサポートしていないようで、それでも私の意図では倍精度は制限されています。CGFX は意図された設計であるため、bignum クラスを持たないため、独自に作成するのが最善であると考えました。

符号なし整数のみを使用する C++ でプロトタイプを作成することができましたが、それを CGFX に移動しようとすると、FX Composer 2.5 はそれをコンパイルできなかったようです。符号なし整数、乗算、および加算のみを使用しているため、コードには多くのビットシフト操作が含まれていますが、FX Composer 2.5 によると、私のプロファイルでは使用できません。

この質問には多くのクエリが含まれていることは知っていますが、残念ながら、数値解析、シェーダー プログラミング、またはオープン GL についてはあまり詳しくありません。この時点で、圧倒されているように感じます。また、リークを修正しようとしていることは確かです。スレッジハンマーで。

したがって、これらの質問のいずれかに対する回答があれば、感謝します。

1. CGFX、またはその他のシェーダー言語は、符号なし整数と浮動小数点数のビットシフト演算子をサポートしていますか (浮動小数点数を大きな浮動小数点数に変換するために必要です)?

2. CGFX やその他のシェーダー言語は、倍精度以上の浮動小数点をサポートしていますか?

3. 大きな浮動小数点クラスを作成するのではなく、私の問題に対処するより洗練された数学的な方法はありますか?

もう少し説明が必要な場合やコード スニペットが必要な場合は、お気軽にお問い合わせください。

コードゴルフの通常のルール。これが例としてのPythonでの実装です

結果は次のようになります

画像ライブラリの使用が許可されています。または、ASCIIアートを使用することもできます。このコードは同じことをします

結果

編集：

アスキーアートのルール：

• 行/列のサイズはパラメーター化されており、コードは任意の有効な値で機能する必要があります。
• 反復回数に応じて、密度が少なくとも3レベル異なります（したがって、そこにある私のプロトタイプは準拠していません）
• 水平方向（つまり、私のプロトタイプは準拠していません）
• 重要なパラメータは固定されています（最大反復= 1000、暴走値x x + y y <= 4.0）

グラフィックのルール：

• 行/列のサイズはパラメーター化されており、コードは任意の有効な値で機能する必要があります。
• 少なくとも3レベルの色、グレースケール
• 水平方向（私のプロトタイプは準拠しています）

JComponentを使用してJavaでマンデルブロ集合の実装を作成しましたが、レンダリングすると奇妙な結果が得られます。それに加えて、すべてが正しくコンパイルされます。何が間違っているのかよくわかりません。コードレビューもいただければ幸いです。

ここではスペースを取りすぎるので、私のソースはペーストビンに投稿されています：

JMandelbrot.java Mandelbrat.java

そこで、マンデルブロ フラクタルを生成するための小さなスニペットを書きましたが、それがすべて醜く歪んだ結果になったときの驚きを想像してみてください (下の画像をご覧ください)。なぜこれが起こるのかという方向性のポイントをいただければ幸いです。これは学習体験であり、私のために誰かを探しているわけではありませんが、デバッグで行き詰まっています。問題のある生成コードは次のとおりです。

そして、画像コード（私はかなり自信を持っています）は次のとおりです。

この魅力的な本の中で、遺伝的プログラミングを使用して画像をインタラクティブに進化させる方法についての章を読んでいます。関数セットのほとんどは、単純な算術関数と三角関数 (実際には画像を操作して返す関数) で構成されています。これらの関数は、画像をエンコードする解析ツリーの内部ノードを構成します。ツリーの葉、または最終値は、乱数と x、y 座標です。

複素平面の反復関数を関数セットに追加するセクションがあります。

遺伝学が特定のマンデルブロ集合を茂みのある木のどこかにノードとして挿入するとします。この関数は 2 つの引数を必要とします: mandel(cReal, cImag) で、それらを複素平面の実座標と虚座標として扱います。ゲノムがたまたまピクセル座標 (x,y) を提供し、mandel() がルート ノードであった場合、おなじみの Mset が得られます。しかし、cReal と cImag 自体が関数の分岐全体の結果である可能性が高く、座標 x、y の多くのインスタンスが葉の間に散らばっています。反復ループに入り、しばらく周回し、最後に Mset アトラクタまでの距離 (反復回数など) を測定して脱出します。

私の質問は、複素平面上の点の実座標と虚座標を引数として取り、マンデルブロ集合のレンダリングを返す関数として、マンデルブロ集合レンダラーをどのように作成しますか?