C++ exp LUT(查找表)

Question

在我正在编写的 C++ CPU 绑定(bind)模拟中，我通过程序中的 valgrind 将瓶颈追踪到 cmath::exp。它目前占用了我 40% 以上的模拟时间。我可以将输入绑定(bind)到一个相对较小的域，但我想控制准确性。我正在考虑转向 LUT(查找表)来替换 exp 但我不太确定如何以“正确的方式”(tm) 执行此操作。我的顾虑:

1. 大型查找表将无法放入缓存，从而降低访问速度
2. 将 double 输入转换为整数以访问查找表的最佳方法
3. (2) 的答案是否取决于输入函数的斜率？
4. 我是在重新发明轮子吗 - 以前有人这样做过吗？

为 exp 实现/(从库中包含)LUT 的最佳方法是什么？

Answer 1

1. 最佳查找表大小取决于您在性能、准确性和实现复杂性之间做出的权衡。你将不得不剖析，我们不能告诉你答案(我们不知道答案)。

2. 使用 lrint来自 <math.h>转换 double至 long int .我不确定它是否在 <cmath> 中.

3. 我不确定斜率与将 float 转换为整数有什么关系。你能详细说说你担心的是什么吗？

4. 是的，您正在重新发明轮子。你正在做的事情已经被任何曾经实现过数学库的人一遍又一遍地做过。有很多关于这个主题的文献。

直接查找表远非最佳。您将需要使用某种多项式逼近，也许是从查找表中选择系数的分段逼近。对于像 exp 这样平滑且可预测的函数，对于相同的计算量，多项式将为您提供更高的精度。所需的多项式将取决于复杂性和准确性之间的权衡，以及您是要最小化预期误差、最小化最大误差还是使用其他一些损失函数。

限制 exp 的域实际上并没有多大帮助，因为它很容易扩展到整个域。

// only works for x in [0, 1]
double exp2_limited(double x);

// works for all x, but doesn't handle overflow properly
double exp2(double x)
{
    return scalbn(exp2_limited(fmod(x, 1.0)), (long) floor(x));
}

总结:

• 在设计这样的函数之前，您必须知道所需的精度。

• 您还必须知道损失函数(即，选择损失函数)。

• 您必须进行剖析才能知道它有多快。

• 使用多项式。