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

Question

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

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

Answer 1

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

如果您足够幸运，您可以获得一个预先计算的查找表 pow2to10，从 2k 可能的二进制指数到它可能的 10 次方。为 10 的幂创建另一个查找表 lookup10。现在您的计算如下:

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

现在您有 3 次数组查找、一次比较和一次乘法，而不是一系列乘法。如果您在紧密循环中执行此操作，请将 pow2to10 存储为 short int 数组，尝试将范围调整到您需要的范围，查找将在适合一级缓存的数据结构。

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