通过修改的exp替换最快的pow().通过计算较低功率时的平方

Question

编辑:

目标: 通过从公共变量的功率计算中重新使用预先计算/缓存的功率,
生成一种无处不在的方法,以获得优于内置功能的自定义功率函数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乘法 .....但使用r2和r6我们有

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

.... 2 FP乘法 ......换句话说,从"哑"指数到正方形到我修改过的exp.通过使用公共指数预处理的正方形,我在乘法方面减少了50%的计算成本...至少在考虑内存成本之前.

真实的表现

使用我当前的方法(编译gcc -O3)我得到35.1秒.运行我的程序100万个循环,而不是(没有其他修改)56.6秒使用内置的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;
}

好处是我的功能在初步测试中显得很快.坏消息是,它不是很普遍存在的,很长,因为我需要case的语句int从权力8到50左右(甚至可能更高将来).而且每一种情况下,我不得不审视并尝试不同的组合,通过强力推导找到哪种组合r2,r4以及r6产生最少的乘法

有没有人有一个更普遍的解决方案pow(double, int)替换使用基数的预先计算的权力来减少必要的乘法次数,和/或有一个无处不在的理论,如何确定理想的组合,以产生任意n和一些的最小乘法一组预先计算的倍数？

Answer 1

这是一个有点类似于 DP 的算法，它将为您提供给定可用n幂的最小乘法次数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)m_n + 1n+i2n -> (m_n + 1, S)

该算法为您提供了大致的最佳策略O(n_max * #available powers)。我并不认为该算法本身是最高效的，但“即时”使用它肯定没有意义。仅当您有合理的n_max（在您的情况下，100 个当然可以）且有效的方法来存储策略时，它才有用。

需要考虑的两个想法：

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

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