返回 int 的 log10 函数的性能

问题描述 投票：0回答：7

今天我需要一个便宜的 log10 函数，我只使用了 int 部分。假设结果是取整的，那么 999 的 log10 就是 2。我自己写一个函数会有好处吗？如果是这样，哪条路最好走。假设代码不会被优化。

我想到过的 log10 的替代方案；

  • 使用 for 循环除或乘以 10；
  • 使用字符串解析器（可能非常昂贵）；
  • 使用整数 log2() 函数乘以常数。

提前谢谢您:)

c++ optimization integer logarithm
7个回答
39
投票

该操作可以在任何具有计数前导零或类似指令（这是大多数架构）的架构上以（快速）恒定时间完成。这是我用来计算以 10 为基数的位数的 C 代码片段，这本质上是相同的任务（假设有一个类似 gcc 的编译器和 32 位 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 条指令。只要小心谨慎，组装过程中仍可加快速度。

关键的见解是使用（极其便宜的）以 2 为底的对数来快速估计以 10 为底的对数；那时我们只需要与 10 的一次方进行比较即可决定是否需要调整猜测。这比搜索 10 的倍数来找到正确的要有效得多。

如果输入绝大多数偏向一位数和两位数，线性扫描有时会更快；对于所有其他输入分布，此实现往往会轻松获胜。

2
投票

一种方法是用 10 次幂进行循环。可以计算该幂并将其存储在表中。这里是Python的例子：

table = [10**i for i in range(1, 10)]
# [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]

def fast_log10(n):
    for i, k in enumerate(table):
        if n - k < 0:
           return i

使用示例：

>>> fast_log10(1)
0
>>> fast_log10(10)
1
>>> fast_log10(100)
2
>>> fast_log10(999)
2
fast_log10(1000)
3

您也可以对此表使用二分搜索。那么算法复杂度仅为 O(lg(n))，其中 n 是位数。 这里是 C 中的二分搜索示例：

long int table[] = {10, 100, 1000, 10000, 1000000};
#define TABLE_LENGHT sizeof(table) / sizeof(long int)

int bisect_log10(long int n, int s, int e) {
    int a = (e - s) / 2 + s;
    if(s >= e)
        return s;
    if((table[a] - n) <= 0)
        return bisect_log10(n, a + 1, e);
    else
        return bisect_log10(n, s, a);
}

int fast_log10(long int n){
    return bisect_log10(n, 0, TABLE_LENGHT);
}

请注意，对于较小的数字，此方法会比上面的方法慢。 完整代码这里.

2
投票

嗯，有一个古老的备用方法——“穷人的日志功能”。 （如果要处理超过 63 位整数，请将第一个“if”更改为“while”。）

n = 1;
if (v >= 1e32){n += 32; v /= 1e32;}
if (v >= 1e16){n += 16; v /= 1e16;}
if (v >=  1e8){n +=  8; v /=  1e8;}
if (v >=  1e4){n +=  4; v /=  1e4;}
if (v >=  1e2){n +=  2; v /=  1e2;}
if (v >=  1e1){n +=  1; v /=  1e1;}

因此，如果您输入 123456.7，情况如下：

n = 1;
if (v >= 1e32) no
if (v >= 1e16) no
if (v >=  1e8) no
if (v >=  1e4) yes, so n = 5, v = 12.34567
if (v >=  1e2) no
if (v >=  1e1) yes, so n = 6, v = 1.234567
     so result is n = 6

这是使用乘法而不是除法的变体：

int n = 1;
double d = 1, temp;
temp = d * 1e32; if (v >= temp){n += 32; d = temp;}
temp = d * 1e16; if (v >= temp){n += 16; d = temp;}
temp = d *  1e8; if (v >= temp){n +=  8; d = temp;}
temp = d *  1e4; if (v >= temp){n +=  4; d = temp;}
temp = d *  1e2; if (v >= temp){n +=  2; d = temp;}
temp = d *  1e1; if (v >= temp){n +=  1; d = temp;}

执行看起来像这样

v = 123456.7
n = 1
d = 1
temp = 1e32, if (v >= 1e32) no
temp = 1e16, if (v >= 1e16) no
temp =  1e8, if (v >=  1e8) no
temp =  1e4, if (v >=  1e4) yes, so n = 5, d = 1e4;
temp =  1e6, if (v >=  1e6) no
temp =  1e5, if (v >=  1e5) yes, so n = 6, d = 1e5;
1
投票

如果您想要更快的对数函数，您需要近似其结果。例如。 exp 函数可以使用“短”泰勒近似来近似。您可以在此处

找到 exp、log、root 和 power 的近似示例

编辑： 您可以在这里找到简短的性能比较

1
投票

因为无符号 

<
或 
>=
测试只需通过减去并检查进位标志即可完成，因此可以将两个数组（
guess
和取反的 
tenToThe
）放入单个 64 位值中，将两者组合起来将数组查找合并为 1，并使用 32 位加法的进位来调整猜测。 
guess[n]
的高32位提供log10(2^n*2-1)的值，而低32位包含
-10^log10(2^n*2-1)
。

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

unsigned int baseTenDigits(unsigned int x) {
    static uint64_t guess[33] = {
      /* 1 */         0, 0, 0, 
      /* 8 */         (1ull<<32)-10, (1ull<<32)-10, (1ull<<32)-10, 
      /* 64 */        (2ull<<32)-100, (2ull<<32)-100, (2ull<<32)-100, 
      /* 512 */       (3ull<<32)-1000, (3ull<<32)-1000, (3ull<<32)-1000, 
                      (3ull<<32)-1000, 
      /* 8192 */      (4ull<<32)-10000, (4ull<<32)-10000, (4ull<<32)-10000, 
      /* 65536 */     (5ull<<32)-100000, (5ull<<32)-100000, (5ull<<32)-100000, 
      /* 524288 */    (6ull<<32)-1000000, (6ull<<32)-1000000, (6ull<<32)-1000000, 
                      (6ull<<32)-1000000, 
      /* 8388608 */   (7ull<<32)-10000000, (7ull<<32)-10000000,
                      (7ull<<32)-10000000, 
      /* 67108864 */  (8ull<<32)-100000000, (8ull<<32)-100000000, 
                      (8ull<<32)-100000000, 
      /* 536870912 */ (9ull<<32)-1000000000, (9ull<<32)-1000000000, 
                      (9ull<<32)-1000000000, 
    };
    uint64_t adjust = guess[baseTwoDigits(x)];
    return (adjust + x) >> 32;
}
0
投票

@StephenCanon 接受的答案的空间优化版本，仅

uint32_t
。使用16字节的单个LUT并正确处理
0
。

#include <limits.h>
#include <stdint.h>

#ifdef _MSC_VER
#include <intrin.h>
#pragma intrinsic(_BitScanReverse)
#endif

static inline unsigned msb(const unsigned x)
{
    unsigned lz;
#ifdef _MSC_VER
    (void) _BitScanReverse(&lz, x);
#else
    lz = __builtin_clz(x);
#endif
    return ((sizeof(x) * CHAR_BIT) - 1) - lz;
}

static unsigned b10digits(const uint32_t x)
{
    static const uint16_t lut[8] = { 0, 2, 13, 69, 347, 1736, 8680, 43402 };
    const unsigned
        shr = (msb(x | 1) & ((sizeof(x) * CHAR_BIT) - 2)) << 1,
        dig = (0x8877665433221100ull >> shr) & 0xF,
        val = lut[(0x07D63440u >> (dig * 3)) & 0x7],
        p10 = ((val << dig) + (~((unsigned)-1 << dig) & 0xC7)) * 90 + 10;
    return dig + (x >= p10 ? 2 : 1);
}
-1
投票

没有任何具体说明，我只是给出一个笼统的答案：

日志函数在大多数语言中都非常有效，因为它是一个基本函数。

您只对整数感兴趣这一事实可能会给您带来一些影响力，但这可能不足以轻松击败内置标准解决方案。

我能想到比内置函数更快的几件事之一是表查找，因此，如果您只对 10000 以下的数字感兴趣，您可以简单地创建一个表，您可以使用它来查找任何当您需要这些值时。

显然这个解决方案无法很好地扩展，但它可能正是您所需要的。

旁注：例如，如果您要导入数据，实际上查看字符串长度可能会更快（而不是先将字符串转换为数字然后查看字符串的值）。当然，这需要输入以正确的格式存储，否则它不会给你带来任何好处。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.