11

Greetings. I'm trying to approximate the function

Log10[x^k0 + k1], where .21 < k0 < 21, 0 < k1 < ~2000, and x is integer < 2^14.

k0 & k1 are constant. For practical purposes, you can assume k0 = 2.12, k1 = 2660. The desired accuracy is 5*10^-4 relative error.

This function is virtually identical to Log[x], except near 0, where it differs a lot.

I already have came up with a SIMD implementation that is ~1.15x faster than a simple lookup table, but would like to improve it if possible, which I think is very hard due to lack of efficient instructions.

My SIMD implementation uses 16bit fixed point arithmetic to evaluate a 3rd degree polynomial (I use least squares fit). The polynomial uses different coefficients for different input ranges. There are 8 ranges, and range i spans (64)2^i to (64)2^(i + 1). The rational behind this is the derivatives of Log[x] drop rapidly with x, meaning a polynomial will fit it more accurately since polynomials are an exact fit for functions that have a derivative of 0 beyond a certain order.

SIMD table lookups are done very efficiently with a single _mm_shuffle_epi8(). I use SSE's float to int conversion to get the exponent and significand used for the fixed point approximation. I also software pipelined the loop to get ~1.25x speedup, so further code optimizations are probably unlikely.

What I'm asking is if there's a more efficient approximation at a higher level? For example:

  1. Can this function be decomposed into functions with a limited domain like log2((2^x) * significand) = x + log2(significand)

hence eliminating the need to deal with different ranges (table lookups). The main problem I think is adding the k1 term kills all those nice log properties that we know and love, making it not possible. Or is it?

  1. Iterative method? don't think so because the Newton method for log[x] is already a complicated expression

  2. Exploiting locality of neighboring pixels? - if the range of the 8 inputs fall in the same approximation range, then I can look up a single coefficient, instead of looking up separate coefficients for each element. Thus, I can use this as a fast common case, and use a slower, general code path when it isn't. But for my data, the range needs to be ~2000 before this property hold 70% of the time, which doesn't seem to make this method competitive.

Please, give me some opinion, especially if you're an applied mathematician, even if you say it can't be done. Thanks.

4

3 に答える 3

2

1 つの観察: 項 x^k0 が近似のために十分に k1 を支配するように、k0 と k1 の関数として必要な x の大きさの式を見つけることができます。

x^k0 +k1 ~= x^k0 であり、関数を次のように概算できます。

k0*Log(x)。

これにより、ある値を超えるすべての x が処理されます。

于 2011-01-16T15:19:32.877 に答える
2

Chebyshev approximationを使用して、最小二乗フィッティングを改善できるはずです。(アイデアは、範囲内の最悪の場合の偏差が最小になる近似を探しているということです。最小二乗は、代わりに、二乗和の差が最小になる近似を探します。)これは大きな違いにはならないと思います。あなたの問題についてはわかりませんが、分割する必要がある範囲の数を多少減らすことができれば幸いです。

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

私はここではアマチュアです。まだ多くの回答が得られていないので、足を踏み入れているだけです。

于 2011-01-16T20:46:35.620 に答える
0

私は最近、sRGB モデルが物理的な三刺激値を格納された RGB 値に圧縮する方法を読みました。

基本的には、部分的に定義されていることを除いて、近似しようとしている関数と非常によく似ています。

k0 x, x < 0.0031308

k1 x^0.417 - k2 それ以外の場合

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

今のところ、関数を正確に近似するわけではありませんが、これが最善のアプローチであると結論付けています。難しいのは、この変更を提案し、人々にそれを使用するよう説得することです。

于 2011-02-08T01:37:19.570 に答える