algorithm - 如何有效地移动数字中的小数点直到达到某个阈值

Question

假设我有一个双 x，其值 > 0 且 < 100 万。我想将它的小数点左移，直到 > 100 万且 < 1000 万。例如，23.129385 变为 2313938.5。

我现在所做的只是乘以 10 直到达到停止条件。但是我经常执行这个算法，所以如果我能以某种方式优化它会很有帮助。一个恒定时间的解决方案，与 x 的大小无关，显然是理想的，但到目前为止我还没有想出一个。

标签： algorithmmathperformance

Answer 1

某些语言，例如带有frexp的 C++ ，将二进制指数公开为整数非常便宜。

如果你很幸运，你可以有一个预先计算的查找表pow2to10，从 2k 可能的二进制指数到它可能的 10 次方。lookup10为 10 的幂创建另一个查找表。现在您的计算如下所示：

frexp(x , &n);
int i = pow2to10[n];
if (lookup10[i+1] <= x) {
    i++;
}
double result = x * lookup10[i];

现在，您有 3 个数组查找、一个比较和一个乘法，而不是一系列乘法。如果您在紧密循环中执行此操作，请将其存储pow2to10为 的数组short int，尝试将范围修剪为您需要的范围，并且查找将位于可以适合 L1 缓存的数据结构中。

如果你不是那么幸运，你可以代替重复乘法，只需与一组已知的 10 次幂进行比较。请注意，如果你有高级语言，你可能会发现运行指令的开销超过了节省比较与相乘。进行二进制搜索以减少查找可能很诱人，但我敢打赌线性搜索会更好，因为这有助于分支预测。