7

在我正在编写的受 C++ CPU 限制的模拟中，我通过程序中的 valgrind 将瓶颈跟踪到cmath::exp. 它目前占用了我 40% 以上的模拟时间。我可以将输入绑定到一个相对较小的域，但我想控制准确性。我正在考虑转移到 LUT（查找表）来替换exp，但我不太确定如何以“正确的方式”（tm）做到这一点。我的担忧：

  1. 大型查找表将不适合缓存，从而减慢访问速度
  2. 将双精度输入转换为整数以访问查找表的最佳方法
  3. (2) 的答案是否取决于输入函数的斜率？
  4. 我是在重新发明轮子吗？以前已经做过了吗？

实现/（从库中包含）LUT 的最佳方法是什么exp？

4

3 回答 3

1

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

  2. 使用lrintfrom<math.h>转换double为long int. 我不确定它是否在<cmath>.

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

  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));
}

概括：

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

  • 您还必须知道损失函数（即选择损失函数）。

  • 在你知道它有多快之前，你必须先分析一下。

  • 使用多项式。

于 2012-07-25T21:09:23.830 回答
1

我遇到了这个问题，我拿了一些堆栈样本来诊断它。它的作用是告诉调用来自哪里以及参数值是什么。我发现当exp从特定位置调用时，参数值是高度可重复的。

这提出了一种记忆方法，这产生了巨大的变化。

它需要一个简单的“包装器”功能：

double exp_cached(double arg, double* old_arg, double* old_result){
  if (arg== *old_arg) return *old_result;
  *old_arg = arg;
  *old_result = exp(arg);
  return *old_result;
}

在exp(foo)过去被称为的地方，请执行以下操作：

static double old_arg = -999999999, old_result;
...
... exp_cached(foo, &old_arg, &old_result)...

这样，exp如果它在调用它的地方的参数具有与以前相同的参数值，则不会被调用。

于 2012-07-26T12:01:47.710 回答
0

之前有人问过一个非常相似的问题。这是我的答案：

该方法是由该问题的作者提出的，我能够有效地实现它（查找表小，查找后的额外工作最少）。它在 C# 中，但转换为 C++ 应该很简单，如果您遇到麻烦，我可以提供帮助。

于 2012-07-25T21:14:00.993 回答