在Python中使用递归计算日志

Question

def recursivelog(n, x, b):
    assert n >= 0
    assert x >= 1
    assert isinstance(b, int) 
    assert b >= 2
    float(x)  # this statement does not change x so is useless here
    if(x < b):
        return 0
    else:
        return 1+ recursivelog(n-1, x/b, b)

n表示步骤数（或递归调用）

x要计算其对数的数字

b对数的底

而结果将舍入到最接近的正整数

^{pr2}$

如何得到实数结果？在

Answer 1

递归算法的思想是让它们递归，直到达到基本情况。截断递归算法可能会导致意外的结果和错误，特别是在有挂起的计算时。在

整数对数可以（应该）计算而不必处理浮点运算。考虑对数的实际意义：log(x, base) == c表示base ** c == x。在外行人的术语中，一个人自身乘以base多少次才能得到x一个人需要将x除以另一个人的base多少次才能得到c。在

在你的问题中，你想要的是整数对数，所以我们执行整数除法。这是你重新提出的问题： 一个人需要用（整数除法）x除以另一个人的base得到{}。在

这样，程序就可以很容易地执行：

def rec_ilogn(x, n):
    """return the integer logarithm of x to base n"""
    assert x > 0, "Real logarithms are only defined for x > 0"
    if x < n:
        return 0
    return 1 + rec_ilogn(x//n, n)

现在要测试代码：

^{pr2}$

Answer 2

你可以做的一件事是在这里使用二进制搜索。 下面这样的方法应该有效：

def calculate_log(lo, hi, val, base, level=0):
    level += 1
    if level > 100:
        return (lo+hi)/2.0
    mid = (lo + hi)/2.0
    if pow(base, mid) == val:
        return mid
    if pow(base, mid) < val:
        return solve(mid, hi, val, base, level+1)
    return solve(lo, mid, val, base, level+1)

你可以做些调整来改善。如果你担心效率，你可以使用你的算法，直到你的函数返回一个小于基数的值。您可能应该使用它来计算小于基数的值的日志。在