对数整数整数

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操作找到2为底的对数（虽然我不认为Python提供这样的功能） 。 x86为此提供了bsr指令。这也是针对任意精度整数的少数操作之一，它可以是恒定的时间（尽管这取决于实现，内存存储等）。

• 一旦你有一个基本2对数，你可以用它整数除法计算到任何电力的-2。

• 如果你只使用相同的基极b，和输入由D ^ķ界，你可以使用的b相二进制搜索相结合的权力，这会为O的预先计算的查找表（日志（ k）* log（n））为任意精度整数（log（k）为搜索，log（n）为每个不等式比较）。

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

• 你最初的想法，用误码分析相结合，可以快速计算某些情况下，那么你可以在不精确的人回落。 Python不为2个参数的log提供误差范围（但不是很大，因为您提供的例子应该是准确的），但现在最得体的数学库，能够计算出1 - 参数log 1个ULP内（单位在最后一个地方），并且将浮点和浮点除法转换为1/2 ulp以内，总的相对误差为3 ulps（因为这些都是乘法），假设您的基数可以精确地表示为浮点数（即不是像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))