我有 32-8191 范围内的整数值,我想将其映射到大致对数刻度。如果我使用基数 2,我可以只计算前导零位并将它们映射到 8 个槽中,但这太粗略了;我需要 32 个槽(更多会更好,但我需要它们映射到 32 位值中的位),结果得出对数的底数大约为 1.18-1.20。谁有一些技巧可以非常快速地计算此值或合理的近似值?
我的直觉是使用条件将范围分解为 2 或 3 个子范围,并为每个子范围使用一个小的查找表,但我想知道我是否可以使用 count-leading-zeros 做一些技巧然后改进结果,尤其是因为结果不必是精确的,而只是大致的对数。
最佳答案
为什么不使用前导位以外的下两位。您可以先将数字划分为 8 个 bin,接下来的两位将每个 bin 进一步划分为四个。在这种情况下,您可以使用非常快速的简单移位操作。
编辑:如果您认为使用对数是一个可行的解决方案。这是一般算法:
令a
为对数的底,取值范围为(b_min, b_max) = (32,8191)
。您可以使用以下公式找到基数:
log(b_max/b_min) / log(a) = 32 bin
它给你 a~1.1892026
。如果使用这个 a 作为对数的底数,则可以将范围 (b_min, b_max)
映射到 (log_a(b_min), log_a(b_max)) = (20.0004,52.0004)
。
现在您只需将所有元素减去 20.0004
即可得到范围 (0,32)
。它保证所有元素都是对数均匀的。完成
注意:由于数值错误,任何一个元素都可能超出范围。具体值需要自己计算。
注2:log_a(b) = log(b)/log(a)
关于c - 特殊情况的快速整数对数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4415231/