より速い数学アルゴリズムが精度を犠牲にする

Question

私は物理学とレンダリングのために非常に多くの数学関数を呼び出すゲームを開発しています。 Quake3で使用されている"Fast inverse sqrt"はsqrt（）より高速で、その背景は美しいと知られています。

通常のアルゴリズムよりも速く、許容可能な精度の低下を伴うアルゴリズムを知っていますか？

Answer 1

これらのアルゴリズムは、文献では「近似アルゴリズム」と呼ばれています。多くの例を持つ標準的な本はApproximation Algorithms by Vijay V. Vaziraniです。

sin x ~~xの場合は、少し一般的です。関数のTaylor series（または周期関数の場合はフーリエ級数）を見て、最初の数項だけを計算します。

もう1つ（やや残酷な）テクニックは、あなたの関数のいくつかの点をランダムにアセンブルし、それに対して線形回帰を実行することです。そうすれば、関数を記述する良い多項式を得ることもできます:)。小さなxの

Answer 2

：罪（x）は〜= xは確率論何が通常、このようなものです多くの場合、物理

Answer 3

で使用されるものです。シミュレーションを10回実行するほうが速くなりますが、シミュレーションを1000回実行するよりも精度の低い結果が得られます。

Answer 4

Nikoには古いファッションルックアップテーブルを追加するための良い提案がいくつかあります。

私は、高性能リアルタイムシステムで循環関数（sin/cos/tan）のルックアップテーブルを何度も成功裡に使用しました。 sqrt（）はこのように難しくなりますが、入力範囲が制限されている（画面のピクセルなど）場合は、速度を上げるのが難しく、スペース/精度を正確に調整することができます。また、一般的な範囲のルックアップを使用して、まれなケースのフレームワークsqrt（）関数にフォールアウトすることもできます。

ポール

Answer 5

（最も一般的な数学演算を含む）任意の連続関数はよく多項式によって境界間隔で近似することができます。これは、一般的な数学関数が（加算法則などの）法則やテーブルルックアップを満たす比較的簡単なアイデンティティと共に、高速近似アルゴリズムを構築するための標準的な手法の基礎を提供します（システム計算で使用されるような高精度メソッドの基礎としょうかん）。

通常、テイラーシリーズは貧しい選択ですが、 ChebyshevまたはMinimaxの多項式は、ほとんどの計算用途ではるかに優れた誤差特性を持っています。ミニマックス多項式をフィッティングするための標準的な手法は、数多くの市販の数学ソフトウェアで実装されているRemes 'Algorithmを使用することです。何をしているのか分かっていれば、1日の作業で独自の実装をロールバックできます。それは浮動小数点の平方根の逆数推定値命令（SSEのrsqrtss/rsqrtps、NEON上vrsqrte、vrsqrtefpを使用することは実質的に高速であるとして、レコード、「高速逆平方根」については

は、最近のプロセッサ上で避けるべきですAltiVec上で）。現在のIntelプロセッサでは、（近似していない）ハードウェアの平方根でさえ非常に高速です。

Answer 6

SQRTを（使用せずに2つの2D点間の近似距離）や三角関数の運命のソースコードは、より：x >> 1をx/2と同じであるがわずかに速いこと

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy) 
{ 
    dx = abs(dx); 
    dy = abs(dy); 
    if (dx < dy) 
     return dx+dy-(dx>>1); 
    else 
     return dx+dy-(dy>>1); 
} 

注 - 良いモダンコンパイラ最近は自動的にこれをやるが、その後はそれほど大きくはなかった。