1

Y値は同じですが、X値が異なる一連のポイントを処理しています。Xを1つ増やしてポイントを確認します。たとえば、Y = 50で、Xは-30から30までの整数です。私のアルゴリズムの一部には、各ポイントから原点までの距離を見つけて、さらに処理を行うことが含まれます。

プロファイリング後、距離計算でのsqrt呼び出しにかなりの時間がかかっていることがわかりました。距離を計算する反復的な方法はありますか？

言い換えると：

効率的に計算したい： r[n] = sqrt(x[n]*x[n] + y*y))。前の反復からの情報を保存できます。各反復はxをインクリメントすることによって変化するため、x[n] = x[n-1] + 1。sqrtまたはtrig関数は、各スキャンラインの先頭を除いて遅すぎるため、使用できません。

十分に良好で（0.1％未満の誤差）、導入された誤差が滑らかである限り（事前に計算された近似の表にビニングすることはできません）、近似を使用できます。

追加情報：xとyは常に-150から150までの整数です

明日、いくつかのアイデアを試して、どれが最も速いかに基づいて最良の答えをマークします。

結果

私はいくつかのタイミングをしました

  • 距離式：16ミリ秒/反復
  • ピートの相互作用ソリューション：8ミリ秒/反復
  • wrang-wrang事前計算ソリューション：8ms/反復

私は両方の答えが好きなので、テストが2つの間で決定することを望んでいました。使用するメモリが少ないので、Pete'sを使用します。

4

6 に答える 6

4

ちょうどそれを感じるために、あなたの範囲y = 50、x=0はr=50およびy=50、x = +/- 30はr〜=58.3を与えます。+/- 0.1％、または+/-0.05絶対値に適した近似値が必要です。これは、ほとんどのライブラリsqrtよりもはるかに低い精度です。

2つの近似アプローチ-前の値からの補間に基づいてrを計算するか、適切な系列のいくつかの項を使用します。

前のrからの補間

r =（x 2 + y 2）1/2

dr / dx=1/2。2x。（x 2 + y 2）-1/2 = x / r

    double r = 50;
    
    for ( int x = 0; x <= 30; ++x ) {
        
        double r_true = Math.sqrt ( 50*50 + x*x );
        
        System.out.printf ( "x: %d r_true: %f r_approx: %f error: %f%%\n", x, r, r_true, 100 * Math.abs ( r_true - r ) / r );
        
        r = r + ( x + 0.5 ) / r; 
    }

与える：

x: 0 r_true: 50.000000 r_approx: 50.000000 error: 0.000000%
x: 1 r_true: 50.010000 r_approx: 50.009999 error: 0.000002%
....
x: 29 r_true: 57.825065 r_approx: 57.801384 error: 0.040953%
x: 30 r_true: 58.335225 r_approx: 58.309519 error: 0.044065%

これは0.1％のエラーの要件を満たしているように見えるので、かなり多くの計算ステップが必要になるため、次のコードをわざわざコーディングしませんでした。

切り捨てられたシリーズ

ゼロに近いxのsqrt（1 + x）のテイラー級数は

sqrt（1 + x）= 1 + 1/2 x-1/8 x 2 ... +（-1/2）n + 1 x n

Using r = y sqrt ( 1 + (x/y)2 ) then you're looking for a term t = ( - 1 / 2 )n+1 0.36n with magnitude less that a 0.001, log ( 0.002 ) > n log ( 0.18 ) or n > 3.6, so taking terms to x^4 should be Ok.

于 2009-09-14T21:41:54.823 に答える
2 
Y=10000
Y2=Y*Y
for x=0..Y2 do
  D[x]=sqrt(Y2+x*x)

norm(x,y)=
  if (y==0) x
  else if (x>y) norm(y,x) 
  else {
     s=Y/y
     D[round(x*s)]/s
  }

座標が滑らかな場合、アイデアは線形補間で拡張できます。精度を上げるには、Y を増やします。

アイデアは、s*(x,y) が y=Y の線上にあり、距離を事前に計算したことです。距離を取得し、s で割ります。

その平方ではなく、距離が本当に必要だと思います。

速度のためにある程度の精度を犠牲にする一般的な sqrt 実装を見つけることもできるかもしれませんが、FPU ができることを打ち負かすことを想像するのは難しいです。

線形補間により、次のように変更することを意味しますD[round(x)]。

f=floor(x)
a=x-f
D[f]*(1-a)+D[f+1]*a
于 2009-09-14T21:21:43.623 に答える
1

さて、あなたの平方根を最適化しようとすることは常にあります、私が見た中で最も速いものは古いカーマック地震3平方根です：

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

とはいえ、sqrtは非線形であるため、結果を得るために線に沿って単純な線形補間を行うことはできません。最良のアイデアは、テーブルルックアップを使用することです。これにより、データへの非常に高速なアクセスが可能になります。また、整数で反復しているように見えるため、テーブルルックアップは非常に正確である必要があります。

于 2009-09-14T21:35:18.457 に答える
1

これはあなたの質問に実際には答えませんが、役立つかもしれません...

私が最初に尋ねる質問は次のとおりです。

  • 「sqrtは必要ですか？」.
  • 「そうでない場合、sqrts の数を減らすにはどうすればよいですか?」
  • それからあなたの：「残りの平方根を巧妙な計算に置き換えることはできますか？」

だから私はから始めます：

  • 正確な半径が必要ですか、それとも半径の二乗が許容されますか? sqrt には高速な近似がありますが、仕様に対して十分に正確ではない可能性があります。
  • ミラー化された 4 分の 1 または 8 分の 1 を使用して画像を処理できますか? バッチで同じ半径値のすべてのピクセルを処理することで、計算回数を 8 分の 1 に減らすことができます。
  • 半径の値を事前に計算できますか? 処理している画像のサイズの 4 分の 1 (または 8 分の 1) のテーブルのみが必要であり、そのテーブルは 1 回だけ事前計算してから、アルゴリズムを何度も実行するために再利用する必要があります。

したがって、巧妙な数学は最速の解決策ではないかもしれません。

于 2009-09-14T21:24:52.050 に答える
0

まず、x=0 の周りをミラーリングできます (n>=0 を計算するだけでよく、それらの結果を対応する n<0 に複製します)。その後、定数 dx を利用するために sqrt(a^2+b^2) (または対応する sin) の導関数を使用することを検討します。

それが十分に正確でない場合は、これが SIMD にとってかなり良い仕事であることを指摘してもよろしいでしょうか。これにより、SSE と VMX (およびシェーダー モデル 2) の両方で逆数の平方根演算が提供されます。

于 2009-09-14T21:34:41.513 に答える
0

これは、HAKMEM アイテムに関連しています。

ITEM 149 (Minsky): CIRCLE ALGORITHM 点プロット表示でほぼ円を描くエレガントな方法は次のとおりです。

NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X

これにより、原点を中心とする非常に丸い楕円が作成され、そのサイズは初期点によって決定されます。イプシロンは循環点の角速度を決定し、偏心にわずかに影響します。イプシロンが 2 のべき乗である場合、平方根、正弦、余弦はもちろん、乗算も必要ありません。ポイントがすぐに周期的になるため、「円」は完全に安定します。

ディスプレイハックで1つのレジスタを保存しようとしたときに、サークルアルゴリズムが誤って発明されました! Ben Gurley は、わずか 6 ～ 7 個の命令を使用して驚くべきディスプレイ ハックを作成しました。これは大きな驚きでした。でも、基本的にはライン志向でした。曲線があるとワクワクするだろうと思い、最小限の説明で曲線表示のハックを手に入れようとしていました。

于 2009-09-15T13:40:44.850 に答える