算法优化 : Logarithm by calculation or lookup table

Question

我正在尝试优化一个音频算法，它必须在每个步骤中计算如下两种算法。现在我已经读到，没有在多项式时间内运行的对数算法。我的问题是，通过查找表计算所有对数是否有意义，因为它们总是相同的，尽管存在大量内存访问的缺点？

for(int f=1;f<11000;f++){
    for(int fk=1;fk<1000;fk++){
        int k = ceil(12 * log2f((f - 0.5) / fk));
    }
} 

我正在用 C++ 编程。

非常感谢!

Answer 1

如果你真正需要的是

ceil(12 * log2(/* something */))

然后有一个非常简单的 O(1) 计算可以工作，使用只有 12 个值的表。

1. 使用 frexp() 将值拆分为指数和尾数。 (这只是位操作，所以只需要几个周期。)

2. 在预先计算的 2.0 的 12 次方根(除以 2)的幂列表中查找尾数，您最多可以进行四次比较。

3. 结果是 12*(指数 - 1) + 最小根的索引 >= 尾数。

编辑添加:

实际上有一个更好的解决方案，因为 2 的 12 次方的幂分布相当均匀。如果将 [0.5, 1.0)(frexp 返回的尾数的范围)划分为 17 个均匀间隔的子范围，每个子范围将落入两个可能的返回值之一。因此，如果您将每个子范围与根向量中的索引相关联，则只需将目标(在该范围内)与单个根进行比较。

我写连贯的英语已经太晚了，所以你必须满足于代码:

int Ceil12TimesLog2(double x) {
  int exp;
  double mantissa = std::frexp(x, &exp) * 2;
  int idx = indexes[int((mantissa - 1.0) * 17)];
  return 12 * (exp - 1) + (mantissa <= roots[idx] ? idx : idx + 1);
}

// Here are the reference tables.

double roots[12] = {
  0x1.0000000000000p+0,
  0x1.0f38f92d97963p+0,
  0x1.1f59ac3c7d6c0p+0,
  0x1.306fe0a31b715p+0,
  0x1.428a2f98d728bp+0,
  0x1.55b8108f0ec5ep+0,
  0x1.6a09e667f3bccp+0,
  0x1.7f910d768cfb0p+0,
  0x1.965fea53d6e3dp+0,
  0x1.ae89f995ad3adp+0,
  0x1.c823e074ec129p+0,
  0x1.e3437e7101344p+0
};
int indexes[17] = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11 };

我试过了，它使用 OP 中的循环将总计算时间从大约 0.5 秒(对于 log2f)减少到大约 0.15 秒。引用表的总大小为 164 字节。