c - 具有 float 指数的 2 的快速幂 [C]

Question

本质上，我尝试使用在下面的代码中计算的值，但是当我将这些值存储在所有具有自己的速率的对象中时，添加的字节刚好足以导致缓存未命中。使用查找表显然无济于事。

所以我正在寻找一种比使用标准幂函数更快地获取这些值的方法，由于可能的输入非常有限，是否有任何我可以使用的技巧？

static inline
double __attribute(( pure )) get_decay_rate(uint8_t rate)
{
     if(rate >= 128)
     {
          return 65535.0/65536.0;
     }

     double k = pow(2, rate/8.0);
     return (k - 1.0) / k;
}


/* pseudocode:
     double k = (int) pow(2, k/8.0);
     k = (k - 1) / k;
     return log(65535/65536)/log(k);
*/
static inline
uint16_t __attribute(( pure )) get_decay_modulus(uint8_t rate)
{
     if(rate <= 128)
     {
          return 1;
     }
//turns out to be the same as the above pseudocode, for some reason. 
     return pow(2, (rate - 128) / 8.0);
}

Answer 1

走这条线:

double k = pow(2, rate/8.0);

基本上，您在这里所做的是提高 2 的定点数次方。

您可以利用 pow(a, b+c) = pow(a, b) * pow(a, c) 和非整数 = 整数部分 + 小数部分这一事实。因此，您使用定点数的整数部分计算 pow，并将其与小数部分的 pow 相乘。

将 8 个小数指数存储在查找表中:

double fractionalPowersOf2[8];

for(int i = 0; i < 8; i++)
    fractionalPowersOf2[i] = pow(2.0, i / 8.0);

然后你可以这样计算:

double k = (double)(1 << (rate >> 3)) * fractionalPowersOf2[rate & 7];

这会屏蔽小数部分并将其用于表查找，然后使用移位将其乘以 2 的整数部分次方。如果加倍转换太慢，您也可以使用查找表。

您也可以使用一些奇特的 bitmagic 类型方法，通过转换指针等将您的值用作 double 的指数，但这将不可移植。

编辑:正如 user3386109 在评论中指出的那样，如果您打开优化，编译器可能会为您优化 2 的整数次方，因此这段代码可能更快:

 double k = pow(2,rate>>3) * table[rate&7];