计算整数n和b的log(n,b)的底部更好的方法是什么？

Question

我想计算floor(log(n,b))的值，其中n和b都是整数。直接实现这个函数会在稍大一点的n和b值时失败。

# direct implementation
def floor_log(n,b):
    return math.floor(math.log(n,b))

例如，floor_log(100**3, 100) 的计算结果为 2，而不是正确的值 3。

我已经编写了一个工作函数，它重复地除以直到没有余数。

# loop based implementation
def floor_log(n,b):
    val = 0
    n = n // b
    while n > 0:
        val += 1
        n = n // b
    return val

有没有更快或更优雅的方法获得这个解决方案？也许使用内置功能？

- jodag

---

n 和 b 有多大/小是预期的？ - Blender

@Blender 最好能找到适用于所有正的32位整数的解决方案。如果您有不同边界的解决方案，我也会感兴趣。 - jodag

我不知道Python内置或numpy中是否有这样的函数。如果你真的关心这个函数的性能，最好用C实现你的Python版本。 - llllllllll

Answer 1

我发布这个问题已经有一段时间了。最初我接受了trincot's answer，但最近意识到当n变得很大时，它不能始终产生正确的结果。实际上有两个问题。首先，虽然我们可以确定只要n < 2 **（2 ** 53）（可能太大而无法存储在计算机中），math.floor（math.log（n，b））的结果不会偏差超过一个，但事实证明它可能偏差+1或-1。此外，+1的误差并不一定意味着n是b的幂，这是trincot答案所假设的。解决这些问题相对简单:

def floor_log(n, b):
    res = math.floor(math.log(n, b))
    return res + 1 if b**(res+1) <= n else res - 1 if b**res > n else res

或者等价地说：

def floor_log(n, b):
    res = math.floor(math.log(n, b))
    return res + (b**(res+1) <= n) - (b**res > n)

---

测试接近幂次b的边缘情况

for p in [15, 30, 100, 1000]:
    for b in range(3, 50):
        for i in range(-2, 3):
            r, e = floor_log(b**p + i, b), p - (i < 0)
            assert r == e, f'floor_log({b}**{p} + {i}, {b}) = {r} but should be {e}'

- jodag

Answer 2

根据这个答案，我们可以避免使用对数运算符n，只需要对b进行对数运算即可，同时可以证明减少需要检查的情况数量。首先使用位长度作为良好的估计值，然后进行纠正。

from math import log

def floor_log(n, b):
    i = int(log(2, b) * (n.bit_length() - 1)) + 1
    return i - (b ** i > n)

与链接答案中使用的逻辑相同。由于可能重复使用相同的基础，因此可以使用缓存进一步优化：

from functools import lru_cache, partial
from math import log

CACHE_SIZE = 10
log_of_2 = lru_cache(CACHE_SIZE)(partial(log, 2))

def floor_log(n, b):
    i = int(log_of_2(b) * (n.bit_length() - 1)) + 1
    return i - (b ** i > n)

- Simply Beautiful Art