整数的整数底数的对数

Question

我想求整数 n 到整数底数 b 的对数的向上舍入值。在代码中：

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

问题是有时无法用浮点数准确表示该值，从而高估了结果。例如：

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

我该怎么办？减去微小的 epsilon 会在其他地方低估它。有没有办法完全避开浮点计算，有点像使用 base 2?

我可以使用循环求对数，但我想知道是否可以在常数时间内完成此操作。

Answer 1

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

如果您使用的是任意精度整数，那么基本上没有恒定时间算法这样的东西，因为几乎每个操作都至少是 O(log(n))，包括转换为浮点数。

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

你可以使用一个find first set operation to find base-2 logarithm (Python ≥3.1 provides this function through int.bit_length())。 x86 为此提供了 bsr 指令。这也是为数不多的可以是常数时间的任意精度整数操作之一（尽管这取决于实现、内存存储等）。
一旦你有了一个以 2 为底的对数，你就可以用它来计算任何 2 的整数除法幂。
如果您只使用相同的基数 b，并且输入以 b^k 为界，您可以使用预先计算的查找 table b 的幂与二进制搜索相结合，对于任意精度整数（搜索为 log(k)，每个不等式比较为 log(n)）为 O(log(k) * log(n))。
即使不是这种情况，您仍然可以尝试某种二进制搜索：通过平方将指数加倍直到太大，然后从那里进行二进制搜索。
你最初的想法，结合一点错误分析，可以快速计算出一些情况，然后你可以退回到不准确的情况。 Python 没有为 2 参数 log 提供错误界限（但这不是很好，因为你提供的例子应该是准确的），但现在大多数像样的数学库都能够计算 1-参数 log 到 1 ulp 以内（单位在最后一位），并强制转换为 float 和 float division 到 1/2 ulp 以内，给出 3 ulp 的总相对误差（因为这些都是乘法的），假设你的基础是准确地将 table 表示为浮点数（即不是像 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))

整数的整数底数的对数

Logarithm to integer base of integer

floating-point

precision

logarithm

floating-accuracy