返回int的log10函数的性能 [英] performance of log10 function returning an int

问题描述

今天，我需要便宜的log10函数，其中仅使用了int部分。假设结果是下限的，那么999的log10将为2。自己编写一个函数会有益吗？如果是这样，那条路最好。假设代码不会被优化。

Today I needed a cheap log10 function, of which I only used the int part. Assuming the result is floored, so the log10 of 999 would be 2. Would it be beneficial writing a function myself? And if so, which way would be the best to go. Assuming the code would not be optimized.

我已经选择过log10的替代方法；

The alternatives to log10 I've though of;

• 使用for循环除以或乘以10；


• 使用字符串解析器（可能非常昂贵）；


• 使用整数log2（）函数乘以一个常数。

事前感谢：）

推荐答案

该操作可以在具有计数前导零或类似指令的任何体系结构（大多数体系结构）上（快速）恒定时间完成。这是我要计算的C代码段，以10为基数，这基本上是相同的任务（假设是类似gcc的编译器和32位int）：

The operation can be done in (fast) constant time on any architecture that has a count-leading-zeros or similar instruction (which is most architectures). Here's a C snippet I have sitting around to compute the number of digits in base ten, which is essentially the same task (assumes a gcc-like compiler and 32-bit int):

unsigned int baseTwoDigits(unsigned int x) {
    return x ? 32 - __builtin_clz(x) : 0;
}

static unsigned int baseTenDigits(unsigned int x) {
    static const unsigned char guess[33] = {
        0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
        3, 3, 3, 3, 4, 4, 4, 5, 5, 5,
        6, 6, 6, 6, 7, 7, 7, 8, 8, 8,
        9, 9, 9
    };
    static const unsigned int tenToThe[] = {
        1, 10, 100, 1000, 10000, 100000, 
        1000000, 10000000, 100000000, 1000000000,
    };
    unsigned int digits = guess[baseTwoDigits(x)];
    return digits + (x >= tenToThe[digits]);
}

GCC和clang在x86上将其编译为大约10条指令。小心一点，可以使组装过程更快速。

GCC and clang compile this down to ~10 instructions on x86. With care, one can make it faster still in assembly.

关键见解是使用（极其便宜的）基数对数以快速估算基数。 -十个对数；到那时，我们只需要与10的单次幂比较就可以决定是否需要调整猜测。这比搜索十个整数的幂要高效得多。

The key insight is to use the (extremely cheap) base-two logarithm to get a fast estimate of the base-ten logarithm; at that point we only need to compare against a single power of ten to decide if we need to adjust the guess. This is much more efficient than searching through multiple powers of ten to find the right one.

如果输入绝大多数被压成一位数和两位数，则线性扫描有时会更快；对于所有其他输入分配，此实现往往很容易取胜。

If the inputs are overwhelmingly biased to one- and two-digit numbers, a linear scan is sometimes faster; for all other input distributions, this implementation tends to win quite handily.

这篇关于返回int的log10函数的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！