python - 计算整数 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

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

Answer 1

我发布这个问题已经有一段时间了。我最初接受了trincot's answer但最近意识到当 n 时它无法始终如一地产生正确的结果变大。确实有两个问题。首先，虽然我们可以确定 math.floor(math.log(n, b)) 的结果只要 n < 2**(2**53) 就不会超过一个(这可能太大而无法存储在您的计算机中)，事实证明它可以关闭 +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}'