11

问候。我正在尝试近似函数

Log10[x^k0 + k1]，其中 0.21 < k0 < 21, 0 < k1 < ~2000，x 是整数 < 2^14。

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

这个函数实际上与 Log[x] 相同，除了在 0 附近，它有很大不同。

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

我的 SIMD 实现使用 16 位定点算法来评估 3 次多项式（我使用最小二乘拟合）。多项式对不同的输入范围使用不同的系数。有 8 个范围，范围 i 跨越 (64)2^i 到 (64)2^(i + 1)。这背后的原因是 Log[x] 的导数随 x 迅速下降，这意味着多项式将更准确地拟合它，因为多项式完全适合导数为 0 的函数超过一定阶数。

使用单个 _mm_shuffle_epi8() 可以非常有效地完成 SIMD 表查找。我使用 SSE 的 float 到 int 转换来获得用于定点逼近的指数和有效数字。我还对循环进行了软件流水线处理，以获得约 1.25 倍的加速，因此可能不太可能进一步优化代码。

我要问的是在更高级别是否有更有效的近似？例如：

  1. 这个函数是否可以分解为具有有限域的函数，如 log2((2^x) * significand) = x + log2(significand)

因此无需处理不同的范围（表查找）。我认为的主要问题是添加 k1 术语会杀死所有我们知道和喜爱的漂亮日志属性，使其成为不可能。或者是吗？

  1. 迭代法？不要这么认为，因为 log[x] 的牛顿法已经是一个复杂的表达式

  2. 利用相邻像素的局部性？- 如果 8 个输入的范围在相同的近似范围内，那么我可以查找单个系数，而不是为每个元素查找单独的系数。因此，我可以将其用作快速的常见情况，并在不是时使用较慢的通用代码路径。但就我的数据而言，在此属性保持 70% 的时间之前，范围需要为 ~2000，这似乎并没有使这种方法具有竞争力。

请给我一些意见，尤其是如果您是应用数学家，即使您说做不到。谢谢。

4

3 回答 3

2

您应该能够通过使用Chebyshev approximation来改进最小二乘拟合。（这个想法是，你正在寻找一个范围内最坏情况偏差最小的近似值；最小二乘法而是寻找总平方差最小的近似值。）我猜这并没有太大的区别对于您的问题，但我不确定-希望它可以在一定程度上减少您需要拆分的范围数量。

如果已经有 的快速实现log(x)，则可以计算P(x) * log(x)其中 P(x) 是由切比雪夫近似选择的多项式。（而不是尝试将整个函数作为多项式近似 - 需要更少的范围缩减。）

我是这里的业余爱好者——只是试探一下，因为还没有很多答案。

于 2011-01-16T20:46:35.620 回答
2

一个观察：您可以找到一个表达式，表示 x 需要多大作为 k0 和 k1 的函数，这样术语 x^k0 支配 k1 足以进行近似：

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

k0*Log(x)。

这将处理高于某个值的所有 x。

于 2011-01-16T15:19:32.877 回答
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 回答