c++ - 提高计算1到2之间的数字的log2的性能。

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。

3年前关闭。



Improve this question




我正在尝试使用整数算术运算来计算log2(x)。

输入的x是介于1和2之间的值。

因为这只会产生0，所以所有内容都会预先缩放16。

换一种说法:

该函数采用x * 2^16的整数值而不是x

函数返回log2(x) * 2^16的整数值，而不是log2(x)

这是我的代码:

uint64_t Log2(uint64_t x)
{
    static uint64_t TWO = (uint64_t)2 << 16;

    uint64_t res = 0;

    for (int i=0; i<16; i++)
    {
        x = (x * x) >> 16;
        if (x >= TWO)
        {
            x >>= 1;
            res += 1 << (15 - i);
        }
    }

    return res;
}

我正在寻找的是一种改善循环性能的方法。

最佳答案

当您在评论中说您不想使用基于查找表的解决方案时，我仍然在这里提出一个解决方案。原因很简单:此查找表为516字节。如果我用Log2编译您的-O3，我会得到一个约740字节的函数，因此它位于同一范围。

我没有创造出完全适合您的解决方案。原因很简单:您的版本不太精确。我使用rint(log(in/65536.0f)/log(2)*65536)作为引用。您的版本产生的最差为2，平均差为1.0。提议的版本的最差差异为1，平均差异为0.2。所以这个版本比较准确。

关于性能:我检查了两个微基准测试:

使用简单的LCG随机发生器进行输入。我的版本是，比

快29 倍

线性使用数字0x10000-> 0x20000。我的版本是 17 倍

解决方案非常简单(使用initTable()初始化查找表)，它在表元素之间线性插值:

unsigned short table[0x102];
void initTable() {
    for (int i=0; i<0x102; i++) {
        int v = rint(log(i*0x100/65536.0f+1)/log(2)*65536);
        if (v>0xffff) v = 0xffff;
        table[i] = v;
    }
}

int log2(int val) {
    int idx = (val-0x10000)>>8;
    int l0 = table[idx];
    int l1 = table[idx+1];

    return l0+(((l1-l0)*(val&0xff)+128)>>8);
}

我刚刚玩过桌子，下面是更多结果:

您可以减小表大小以具有0x82元素(260个字节)，并且仍然具有最严重的错误1和0.32的平均错误(在这种情况下，您需要将0.5+放入rint()中)

您可以减小表大小以具有0x42元素(132字节)，最坏的错误变为2，平均错误为0.53(在这种情况下，您需要将0.75+放入rint()中)

减小表大小会进一步显着增加最严重的错误

关于c++ - 提高计算1到2之间的数字的log2的性能。，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45390514/