4

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

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

我正在用 C++ 编程。

非常感谢！

4

4 回答 4

6

如果你真正需要的是

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

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

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

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

  3. 结果是 12*(exponent - 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 字节。

于 2012-10-25T23:42:54.030 回答
2

为简洁明了而写 z 而不是 fk，你的内循环计算ceil(12 * log2f((f - 0.5) / z)). 现在12 * log2f((f - 0.5) / z)= 12*log2f(f - 0.5) - 12*log2f(z)。事先，计算一个包含 999 个条目的数组，允许您只用 11998 个对数计算来计算所有值，而不是其中的 10988001 个：

for (int z=1; z<1000; ++z)
  z12[z] = 12 * log2f(z);

for (int f=1; f<11000; ++f) {
  w = 12 * log2f(f - 0.5);
  for (int z=1; z<1000; ++z) {
    int k = ceil(w - z12[z]);
  }
}
于 2012-10-25T23:36:15.553 回答
1

我发现：

  • 虽然你有 11Kx1K = 11M 的组合(f, fk)，
  • k 的不同值的数量只有 294。（你只需要 9 位来表示它）。

所以绝对可以构造一个二维数组来存储映射并将其加载到内存中。看起来像

LOOKUP[f][fk] = v, f in 1..11000, fk in 1..1000 
--------------------
v1,1 v1,2 v1,3 ... v1,1000
v2,1 v2,2 v2,3 ... v2,1000
...    ...    ...  ...
v11000,1 , ...     v11000,1000

由于每个v是两个字节，因此您只需要 11Kx1Kx2B = 22MB 内存即可加载此表。没什么。

于 2012-10-25T23:16:57.390 回答
0

如果循环顺序相反，则 k 的重复值的数量会更高。在该集合中只有 12977 个案例，其中 k 有“一个”；最长的一次是618。

这表明反向方法可以最大限度地减少 log2f 调用的次数——必须计算索引n，其中 k(z,f+n) != k(z,f) （并循环 n 个实例......）

无论如何，在最终产品中，我怀疑巨大 LUT 的好处。即使是使用 11000 + 1000 大小的表的方法对我来说似乎也不是最理想的。相反，我猜只有 11000 + 1000 个整数存在一个线性或最大 2 次分段多项式逼近 log2，它由 8 到 16 个部分组成。

如果找到了这种方法，那么多项式系数将适合 NEON 或 XXM 寄存器，并允许在没有内存访问的情况下并行实现。

于 2012-10-26T07:21:39.147 回答