6

编辑：

目标： 通过重用来自公共变量的幂计算的预先计算/缓存的幂，
生成一种通用的方法来推导自定义幂函数，该函数优于内置函数。pow(double, uint)

已经完成的工作：
我已经导出了一个比内置函数快大约 40% 的函数，但是这是一个蛮力手动导出的函数——我想要一种方法来自动生成这样的幂函数块任意uint权力。

知道

要获得最佳定制pow(double, uint)，您需要一些知识。对于这个问题，已知（澄清）是：

  1. 幂将是一个整数。
  2. 已知最大功率 ( N_MAX)。
  3. 可以（重新）使用的预先计算的幂在编译时是已知的（例如，在我的示例r2中r4， 和r6）。
  4. r2无论其他预先计算的幂如何，都可以假定始终计算平方。

解决方案要求

需要一个单独的程序来编写一个case查找表或预处理器逻辑来生成这样一个表的最佳解决方案是可以接受的，但是，使用手头的权力手动生成（即蛮力派生）查找表的非最佳解决方案将不被接受（因为我已经有了，并在我的例子中展示了这一点......我们的想法是摆脱这个）。

可能的解决途径

作为建议，您知道N_MAX一组预先计算好的权力B（B={2,4,6}以我为例）。您可以在单独的程序中或在预处理器中生成Sq(Bi, x) <= N_MAX . You can use this to form a basis setA , which you then search somehow to determine the least number of terms that can be summed to produce an arbitrary exponent ofn>>1 , wheren<=N_MAX` 的所有平方的表（由于我们通过检查 LSB 来处理奇数情况并乘以 sqrt(r2))。

理论背景

我相信下面的方法正式地是平方指数的修改版本：

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

....它利用了某些低阶幂已经必然预先计算的事实，因此它通过平方（我假设pow(double, int)使用）将乘法的最佳集合从普通指数转移。

然而，通过使用存储的小功率中间体而不是简单的 exp 可以显着节省。由 上的正方形r2。

理论性能

例如，对于一组对象n=14.... 在这种情况下 exp。通过权力给

double r4 = Sq(r2), r14=Sq(r4)*r4*r2; //4 op.

...这需要4 个 FP 乘法..... 但是使用r2andr6我们有

double r14=Sq(r6)*r2; //2 op.

.... 2 FP 乘法.... 换句话说，通过从平方的“哑”幂到我修改后的 exp。通过使用常用指数预缓存的平方，我已经将乘法计算成本降低了 50%……至少在考虑内存成本之前。

真正的表现

使用我当前的方法（用 编译gcc -O3）我得到35.1 秒。运行我的程序的 100 万个周期，而（没有其他修改）56.6 s使用内置的 int pow(double, int).... 所以几乎是理论上的加速。

在这一点上，您可能会摸不着头脑，如何在一条指令行上减少 50% 的乘法运算可以提供约 40% 的加速。但基本上，这行代码每个周期被调用 1,000 多次，是迄今为止整个程序中评估最多/最昂贵的代码行。因此，该程序似乎对该块中的小优化/改进高度敏感。

原始帖子和示例代码

我需要替换pow(double, int)函数，因为我已经计算了 6 次幂并保存了 2 次方和 4 次方中间值，所有这些都可用于减少pow使用相同double基数的第二次调用中的乘法。

更具体地说，在我的 c++ 代码中，我有一个性能关键计算代码片段，其中我将 3D 点之间的距离的倒数提高到 6 次方和 n 次方。例如：

double distSq = CalcDist(p1,p2), r2 = a/distSq, r6 = r2 * r2 * r2;
results += m*(pow(sqrt(r2), n) - r6);

其中m和a是与拟合方程相关的常数，n是任意幂。

一种更有效的形式是：

double distSq = CalcDist(p1,p2), r2 = a/distSq, r6 = r2 * r2 * r2;
results += m*(pow(r2, n)*(n&0x1?sqrt(r2):1.0) - r6);

然而，这也不是最优的。我发现明显更快的是有一个pow使用倍数 r2、r4 和 r6 的自定义函数，无论如何我必须在第二个术语中计算它们。

例如：

double distSq = CalcDist(p1,p2), r2 = a/distSq, r4 = r2 * r2, r6 = r4 * r2;
results += m*(POW(r2, r4, r6 n) - r6);

函数内部：

double POW(double r2, double r4, double r6, uint n)
{
   double results = (n&0x1 : sqrt(r2) : 1.0);
   n >>= 1;
   switch (n)
   {
     case 1:
     ....
     case 12:
        Sq(Sq(r6));

   }
   return result;
}

好消息是我的功能在初步测试中出现得很快。坏消息是它不是很普遍，而且很长，因为我需要从to左右的权力case声明（将来可能会更高）。此外，每种情况我都必须检查并尝试不同的组合，以通过蛮力推导找到 、 和 的哪个组合产生的乘法最少int850r2r4r6

有没有人有一个更普遍的pow(double, int)替代解决方案，它使用预先计算的基数来减少必要乘法的数量，和/或有一个普遍的理论来说明如何确定理想组合以产生任意n和一些的最少乘法一组预先计算的倍数？？

4

1 回答 1

1

这是一个有点类似于 DP 的算法，它将为您提供给定n和可用 power的最小乘法次数x^i，以及通过回溯的最佳策略。对于每个可能的指数n，将第二个数字的对关联起来(minimum number of multiplications to get here, type of multiplication that gets you there)，只需写i或特殊符号S进行平方。

你显然从1 -> (0, /).

给定n -> (m_n, Action_m)，设置n+i ->为(m_n + 1, i)ifm_n + 1小于之前可能计算的最小移动次数n+i。同样，2n -> (m_n + 1, S)如果这比以前的可能解决方案更好，请设置。

该算法大致为您提供最佳策略O(n_max * #available powers)。我并没有声称该算法本身是最有效的，但“即时”使用它肯定是没有意义的。只有当你有一个合理的n_max（100，在你的情况下，当然没问题）和存储策略的有效方法时，它才有用。

需要考虑的两个想法：

(1) 在进行基准测试之前，我不相信它会通过平方（在很大程度上取决于可用的权力，当然）会导致对标准 exp 的巨大性能改进。

(2) 这种策略的数值误差行为（以及平方的 exp）与 完全不同pow(double, double)。

于 2013-09-22T16:37:17.797 回答