21

我正在尝试计算 log a b （并得到一个浮点数，而不是整数）。我打算这样做log(b)/log(a)。从数学上讲，我可以使用任何对cmath数函数（以 2、e 或 10 为底）来进行此计算；但是，我会在我的程序中经常运行这个计算，所以我想知道其中一个是否比其他的快得多（或者更好的是，如果有更快但仍然简单的方法来做到这一点）。如果重要，a 和 b 都是整数。

4

5 回答 5

15

首先，预先计算1.0/log(a)并乘以log(b)该表达式。

编辑：我最初说自然对数（以 e 为底）是最快的，但其他人说以 2 为底由处理器直接支持并且速度最快。我没有理由怀疑它。

编辑2：我最初认为这a是一个常数，但是在重新阅读从未陈述过的问题时。如果是这样，那么预先计算将没有任何好处。但是，如果是，您可以通过适当的可变性名称选择可读性：

const double base_a = 1.0 / log(a);
for (int b = 0; b < bazillions; ++b)
    double result = log(b) * base_a;

奇怪的是，微软不提供 base 2 log 功能，这解释了为什么我不熟悉它。此外，用于计算日志的 x86 指令包括自动乘法，并且不同基数所需的常数也可通过优化指令获得，因此我希望 3 个不同的日志函数具有相同的时序（即使基数 2 也必须相乘由 1)。

于 2011-07-11T20:09:10.110 回答
11

由于b和a是整数，您可以使用位旋转的所有荣耀来找到以 2 为底的日志。这里有一些：

  • 在 O(N) 操作中找到 MSB N 设置的整数的对数基数 2（显而易见的方法）
  • 查找具有 64 位 IEEE 浮点数的整数的整数对数基数 2
  • 使用查找表查找整数的以 2 为底的对数
  • 在 O(lg(N)) 操作中找到 N 位整数的对数底数 2
  • 使用乘法和查找在 O(lg(N)) 操作中找到 N 位整数的对数底数 2

我会留给您选择最适合您需求的“快速日志”功能。

于 2011-07-11T20:18:19.980 回答
4

在我有数据的平台上，log2比其他平台快得多，符合我的预期。但是请注意，差异非常小（只有百分之几）。这真的不值得担心。

写一个清晰的实现。然后测量性能。

于 2011-07-11T20:13:23.297 回答
1

在 8087 指令集中，只有一条以 2 为底的对数指令，所以我猜这个指令是最快的。

当然这种问题很大程度上取决于你的处理器/架构，所以我建议做一个简单的测试并计时。

于 2011-07-11T20:14:21.313 回答
0

答案是：

  • 这取决于
  • 剖析它

你甚至没有提到你的 CPU 类型、变量类型、编译器标志、数据布局。如果你需要同时做很多这些，我相信会有一个 SIMD 选项。只要您使用对齐并清除简单循环（如果您喜欢古老的方法，您的编译器就会优化它）。

很有可能，英特尔编译器在这方面有针对英特尔处理器的特定技巧。

如果你真的想要，你可以使用 CUDA 并利用 GPU。

我想，如果您不幸缺少这些指令集，您可以在位摆弄水平上下降并编写一个可以很好近似的算法。在这种情况下，我可以打赌不止一个苹果派，2-log 会比任何其他 base-log 都快

于 2011-07-11T20:11:46.477 回答