如何精确计算整数的ceil(log_N(i))？浮点实现存精度问题

我需要计算ceil(log_N(i))，其中log_N是底数为正整数N的对数，i同样为正整数。
使用浮点数运算的Python直接实现存在多处精度问题：

import numpy as np

bases = [2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47]

exponents = [1,2,3,4]

for nn in exponents:
  for p in bases:
    i = p**nn
    _ = np.ceil(np.log(i)/np.log(p)) # 预期结果为nn
    if _.astype(int) != nn:
      print(f"Error: log({i})/log({p}) = {_} != {nn}")

运行输出：

Error: log(125)/log(5) = 4.0 != 3; delta = 1.0
Error: log(15625)/log(25) = 4.0 != 3; delta = 1.0
Error: log(103823)/log(47) = 4.0 != 3; delta = 1.0

移除ceil和整数转换操作后，可见部分计算结果存在约4e-16的误差：

Error: log(125)/log(5) = 3.0000000000000004 != 3; delta = 4.440892098500626e-16
Error: log(4913)/log(17) = 2.9999999999999996 != 3; delta = 4.440892098500626e-16
Error: log(15625)/log(25) = 3.0000000000000004 != 3; delta = 4.440892098500626e-16
Error: log(29791)/log(31) = 2.9999999999999996 != 3; delta = 4.440892098500626e-16
Error: log(68921)/log(41) = 2.9999999999999996 != 3; delta = 4.440892098500626e-16
Error: log(103823)/log(47) = 3.0000000000000004 != 3; delta = 4.440892098500626e-16

该误差仅为约2个最低有效位，但方向并不固定。请问是否存在一种总能得到正确结果的方法？

浮点数的精度问题本质是二进制无法精确表示所有十进制对数结果，因此纯整数运算的实现是最可靠的选择，以下是几种可行方案：

方法1：迭代累乘计数 #

通过不断将底数N累乘，直到结果大于等于i，记录乘的次数即可得到结果。逻辑简单，完全规避浮点数问题：

def ceil_log(N, i):
    if i <= 0 or N <= 1:
        raise ValueError("N必须大于1，i必须为正整数")
    if i == 1:
        return 0  # log_N(1)=0，ceil后仍为0
    count = 0
    current = 1
    while current < i:
        current *= N
        count += 1
    return count

测试之前出错的案例：

• ceil_log(5,125) 返回3，正确
• ceil_log(25,15625) 返回3，正确
• ceil_log(47,103823) 返回3，正确

方法2：二进制搜索优化 #

当N和i数值极大时，迭代累乘效率会降低，此时可以用二进制搜索寻找最小的k，使得N^k >= i，效率更高：

def ceil_log_binary(N, i):
    if i <= 0 or N <= 1:
        raise ValueError("N必须大于1，i必须为正整数")
    if i == 1:
        return 0
    low = 0
    high = 1
    # 先找到足够大的上界
    while N**high < i:
        high *= 2
    # 二进制搜索缩小范围
    while low < high:
        mid = (low + high) // 2
        if N**mid >= i:
            high = mid
        else:
            low = mid + 1
    return low

这种方法适合处理大数值输入，结果同样精确。

方法3：修正浮点数运算误差（应急方案，不推荐） #

如果必须使用浮点数运算，可以通过math.isclose判断计算值是否接近整数，再修正结果：

import math

def ceil_log_float(N, i):
    if i <= 0 or N <= 1:
        raise ValueError("N必须大于1，i必须为正整数")
    if i == 1:
        return 0
    log_val = math.log(i, N)
    # 判断是否接近整数
    if math.isclose(log_val, round(log_val)):
        return round(log_val)
    else:
        return math.ceil(log_val)

但这种方法仍依赖浮点数精度，极端场景下可能出错，不如纯整数运算可靠。

内容的提问来源于stack exchange，提问作者user1816847