近似log10 [x^k0 + k1]

Question

おはようございます。私はどこ0.21 < K0 < 21、0 < K1 <〜2000、およびxは、14^2 <整数である、[X^K0 + K1]機能

をLog10を近似しようとしています。

k0 &k1は一定である。実際の目的では、k0 = 2.12、k1 = 2660と仮定することができます。希望の精度は5 * 10^-4相対誤差です。

この関数はLog [x]と事実上同じですが、0に近い点を除き、多くの点が異なります。

シンプルなルックアップテーブルより約1.15倍高速なSIMD実装がすでに用意されていますが、可能な限り改善したいと考えています。これは効率的な命令がないために非常に難しいと思います。

私のSIMD実装では、16進の固定小数点演算を使用して3次多項式を評価します（最小二乗適合を使用します）。多項式は、異なる入力範囲に対して異なる係数を使用します。 8つの範囲が存在し、範囲iは（64）2^iから（64）2 ^（i + 1）に及ぶ。 これは、Log [x]の派生形であり、多項式は特定の次数を超えて0の微分を持つ関数に正確にフィットするため、多項式がより正確にフィットすることを意味します。

SIMDテーブルのルックアップは、単一の_mm_shuffle_epi8（）で非常に効率的に実行されます。 SSEのfloatからintへの変換を使用して、固定小数点近似に使用される指数と仮数を取得します。私もソフトウェアをパイプライン化して〜1.25倍のスピードアップを得ました。したがって、コードの最適化はおそらくほとんどありません。

より高いレベルでより効率的な近似があると私は尋ねています。例えば ：

1. この関数は LOG2（（2^X）*仮数）= X + LOG2（仮）

故に必要性を排除するように制限されたドメインと機能に分解することができます異なる範囲（テーブル参照）を扱う私が思っている主な問題は、k1という言葉を追加することは、われわれが知っていて愛しているすべての素晴らしいログプロパティを殺し、不可能にすることです。またはそれは？

1. 反復法？ log [x]のニュートン法はすでに複雑な式なので、そう思わないでください。

2. 近傍ピクセルの局所性を利用していますか？ - 8つの入力の範囲が同じ近似範囲にある場合、各要素の個別の係数を調べるのではなく、1つの係数をルックアップすることができます。したがって、私はこれを高速の一般的なケースとして使用し、そうでない場合には、より遅く一般的なコードパスを使用します。しかし、私のデータでは、このプロパティが時間の70％を保持する前に範囲を〜2000にする必要があり、これはこのメソッドを競争力のあるものにしていないようです。

特に、あなたがそれができないと言っても、あなたが応用されている数学者なら、私には何か意見をください。ありがとう。

Answer 1

一つの観察： あなたは用語のx^K0は、近似のための十分なK1を支配するようなK0とK1の関数としてである必要がありますどのように大きなxの式を見つけることができます：

のx^K0 + k1〜= x^k0となり、関数をおおよそ評価することができます。

k0 * Log（x）。

これは、すべてのxがある値を超えているかどうかを判断します。

Answer 2

Chebyshev approximationを使用すると、最小自乗フィッティングを改善することができます。 （考え方は、範囲内の最悪の場合の偏差が最小である近似を探していることであり、最小二乗法は、その差の二乗の和が最小のものを探します。）これは大きな違いはないと思いますあなたの問題のために、私は確信していません - うまくいけば、分割する必要がある範囲の数をいくらか減らすことができます。

すでにlog(x)の高速実装がある場合、P(x) * log(x)を計算することもできます。ここで、P（x）はチェビシェフ近似によって選択された多項式です。 （多項式として関数全体を近似しようとするのではなく、より少ない範囲削減を必要とする）

私はここの素人です。 。

Answer 3

最近、sRGBモデルが物理的な3刺激値を格納されたRGB値にどのように圧縮するのかを読みました。

それは区分的に定義されていますことを除いてそれは基本的に、私は近似しようとする機能に非常によく似ています

K0 X、X < 0.0031308

K1のx^0.417 - K2を、私はそう

Log [x^k0 + k1]の定数の追加は、関数の開始をより線形にすることであると言われました。しかし、それは簡単な近似で簡単に達成できます。これにより、近似は2つの近似範囲だけで、より「均一」になります。これは、近似範囲インデックス（整数ログ）を計算する必要がなくなり、SIMD係数ルックアップを行う必要がなくなるため、計算コストが安くなるはずです。

今のところ、関数を正確に近似していなくても、これが最良のアプローチであると結論づけられます。難しい部分は、この変更を提案し、人々にそれを使用するように説得するでしょう。