编辑:
目标: 通过重用来自公共变量的幂计算的预先计算/缓存的幂,
生成一种通用的方法来推导自定义幂函数,该函数优于内置函数。pow(double, uint)
已经完成的工作:
我已经导出了一个比内置函数快大约 40% 的函数,但是这是一个蛮力手动导出的函数——我想要一种方法来自动生成这样的幂函数块任意uint
权力。
知道
要获得最佳定制pow(double, uint)
,您需要一些知识。对于这个问题,已知(澄清)是:
- 幂将是一个整数。
- 已知最大功率 (
N_MAX
)。 - 可以(重新)使用的预先计算的幂在编译时是已知的(例如,在我的示例
r2
中r4
, 和r6
)。 r2
无论其他预先计算的幂如何,都可以假定始终计算平方。
解决方案要求
需要一个单独的程序来编写一个case
查找表或预处理器逻辑来生成这样一个表的最佳解决方案是可以接受的,但是,使用手头的权力手动生成(即蛮力派生)查找表的非最佳解决方案将不被接受(因为我已经有了,并在我的例子中展示了这一点......我们的想法是摆脱这个)。
可能的解决途径
作为建议,您知道N_MAX
一组预先计算好的权力B
(B={2,4,6}
以我为例)。您可以在单独的程序中或在预处理器中生成Sq(Bi, x
) <= N_MAX . You can use this to form a basis set
A , which you then search somehow to determine the least number of terms that can be summed to produce an arbitrary exponent of
n>>1 , where
n<=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
andr6
我们有
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
声明(将来可能会更高)。此外,每种情况我都必须检查并尝试不同的组合,以通过蛮力推导找到 、 和 的哪个组合产生的乘法最少int
8
50
r2
r4
r6
有没有人有一个更普遍的pow(double, int)
替代解决方案,它使用预先计算的基数来减少必要乘法的数量,和/或有一个普遍的理论来说明如何确定理想组合以产生任意n
和一些的最少乘法一组预先计算的倍数??