floating-point - 整数的整数底数的对数

Question

我想找到整数n以整数b为底的对数向上舍入的值。在代码中:

result = int(ceil(log(n, b)))

问题在于有时无法用 float 精确表示该值，从而高估了结果。例如:

log(125, 5) == int(ceil(3.0000000000000004)) == 4

对此我能做什么？减去微小的 epsilon 会在其他地方低估它。有没有办法完全回避浮点计算，就像使用 base 2 时一样？

我可以使用循环来查找对数，但我想知道是否可以在恒定时间内完成此操作。

Answer 1

嗯，你必须小心你所说的恒定时间的含义。如果您正在处理固定宽度的整数，那么一个简单的 for 循环是有界的(以 2 为基数的 64 位整数的最坏情况将是 64 次乘法)，并且可能仍然比转换为 float 更快，调用 log 函数，并截断回整数。

如果您使用任意精度整数，那么基本上不存在恒定时间算法之类的东西，因为几乎每个操作都至少为 O(log(n))，包括转换为 float 。

也就是说，您还可以尝试其他一些方法:

• 您可以使用find first set求以 2 为底的对数的操作(Python ≥3.1 通过 int.bit_length() 提供此函数)。 x86 为此提供了 bsr 指令。这也是对任意精度整数进行的少数几个可能是恒定时间的操作之一(尽管这取决于实现、内存存储等)。

• 一旦有了以 2 为底的对数，就可以用它通过整数除法来计算任何 2 的幂。

• 如果您仅使用相同的基数 b，并且输入以 b^k 为界，您可以使用预先计算的 b 幂查找表与二分搜索相结合，这对于任意精度整数，其复杂度为 O(log(k) * log(n))(log(k) 用于搜索，log(n) 用于每个不等式比较)。

• 即使情况并非如此，您仍然可以尝试某种二分搜索:通过平方将指数加倍，直到指数太大，然后从那里开始二分搜索。

• 您最初的想法与一些错误分析相结合，可以快速计算出一些情况，然后您可以求助于不精确的情况。 Python 没有为 2 参数 log 提供错误界限(但这不是很好，因为您提供的示例应该是准确的)，但现在大多数像样的数学库都能够计算 1 参数log 到 1 ulp 以内(最后一位的单位)，并转换为 float 和浮点除法到 1/2 ulp 以内，给出 3 ulp 的总相对误差(因为这些都是乘法的)，假设你的base 完全可以表示为 float (即不是像 1e30 这样的大整数)。

在Python中，这将是:

import math, sys
def clog(n,b):
    a = math.log(n)/math.log(b)
    r = round(a)
    i = int(r)
    if abs(a-r) <= a*3*sys.float_info.epsilon:
        # slow
        if n > b**i:
            return i+1
        else:
            return i
    else:
        return int(math.ceil(a))