近似log10[x^k0 + k1]

Question

欢迎光临。我在试着逼近这个函数

Log10x^k0 + k1，其中.21 < k0 < 21，0< k1 <2000，x是整数< 2^14。

k0和k1是常数。出于实际目的，您可以假设k0 = 2.12，k1 = 2660。所需精度为5*10^-4相对误差。

这个函数实际上与Logx完全相同，除了在0附近，它有很大的不同。

我已经想出了一个SIMD实现，比一个简单的查找表快1.15倍，但是如果可能的话，我想改进它，我认为这是非常困难的，因为缺乏有效的指令。

我的SIMD实现使用16位不动点算法来评估一个三次多项式(我使用最小二乘拟合)。多项式对于不同的输入范围使用不同的系数。有8个范围，范围i跨越(64)2^i到(64)2^(i + 1)。这背后的有理是Logx的导数随x迅速下降，这意味着多项式将更精确地拟合它，因为多项式是对导数超过某一阶的函数的精确拟合。

SIMD表查找使用单个_mm_shuffle_epi8()非常有效。利用SSE浮点变换得到指数和意义，并用于不动点逼近。我还对循环进行了软件流水线，以获得~1.25x加速比，因此可能不太可能进行进一步的代码优化。

我想问的是，在更高的水平上是否有一个更有效的近似？例如：

1. 该函数是否可以分解为具有有限域的函数，如log2((2^x) *重要)=x+log2(意义)

因此，不需要处理不同的范围(表查找)。我认为主要的问题是添加k1这个术语会扼杀我们所知道和喜爱的所有优秀的日志属性，这使得它不可能实现。还是真的是这样？

1. 迭代法？不要这么认为，因为logx的牛顿方法已经是一个复杂的表达式了
2. 利用邻近像素的局部性？-如果8个输入的范围落在相同的近似范围内，那么我可以查找单个系数，而不是为每个元素查找单独的系数。因此，我可以使用它作为一个快速的公共情况，并使用一个较慢的，一般的代码路径，当它不是。但是对于我的数据，范围需要在这个属性持有70%的时间之前，这个范围需要2000，这似乎没有使这个方法具有竞争力。

请给我一些意见，特别是如果你是一个应用数学家，即使你说它不能做到。谢谢。

Answer 1

一个注意事项:您可以找到一个表达式，表示x作为k0和k1的函数需要有多大，因此，对于近似而言，x^k0这个术语足以支配k1：

x^k0 +k1 ~= x^k0，允许您将函数近似计算为

k0*Log(x)。

这将照顾所有x的高于某个值。

Answer 2

您应该能够改进最小二乘拟合使用切比雪夫逼近.(你的想法是，在一个范围内，最坏情况下的偏差是最小的，而最小二乘法则是求和平方差最小的近似。)我想这不会对你的问题产生太大的影响，但我不确定--希望它能减少你需要分成的范围的数量。

如果已经有了log(x)的快速实现，则可以计算P(x) * log(x)，其中P(x)是由Chebyshev逼近选择的多项式。(与其试图以多项式的方式完成整个函数，而是为了减少范围缩减。)

我是这里的业余爱好者--只是蘸着脚，因为已经没有太多的答案了。

Answer 3

我最近读到了sRGB模型如何将物理三刺激值压缩到存储的RGB值中。

它基本上与我试图近似的函数非常相似，只不过它是按分段定义的：

k0 x，x< 0.0031308

k1 x^0.417 -否则为k2

有人告诉我，Logx^k0 + k1中的常量加法是为了使函数的开头更加线性。但这可以很容易地通过分段近似来实现。这将使近似更“均匀”-只有两个近似范围。由于不再需要计算近似范围索引(整数日志)和执行SIMD系数查找，因此计算起来应该更便宜。

现在，我认为这将是最好的方法，尽管它不能精确地近似函数。困难的部分将是提出这一改变，并说服人们使用它。