是根算法

Question

我创建了一个函数来确定一个数字是否是另一个数字的根（不确定这是否正确）。

def isRoot(n, root):
   return not math.log(n, root)%1

这在大多数情况下都有效，但我发现我遇到了浮点数问题。例如，如果我执行 isRoot(125,5)，我会得到 False。经过一番排查，发现是因为

>>> math.log(125,5)
3.0000000000000004

尽管结果应该是3。所以我的问题是，我应该只使用一种我不知道的不同算法吗？或者有没有办法确保无论我使用多大的数字都能正常工作？

Answer 1

如果您不介意性能下降，可以查看标准库中的 decimal 模块。它有任意精度的数字。

Answer 2

您依赖于一个正好等于 0 (False) 的浮点数来使您的函数正常工作。一般而言，在处理浮点数时应避免进行相等性测试。相反，最好为差异设置可接受的容差水平。

试试这个：

def isRoot(n, root, epsilon=1e-10):
    test = math.log(n, root)%1
    return abs(test - int(round(test))) < epsilon

Answer 3

这个怎么样：

def isRoot(n, root):
    power = 1
    while root ** power < n:
        power += 1
    return root ** power == n

如果这太慢，您还可以进行某种二进制搜索以减少检查次数。

Answer 4

避免该问题的最佳方法是使用完全避免浮点数学运算的不同方法。

def isRoot(n, root):
    return n <= 1 or (False if n % root != 0 else isRoot(n // root, root))

Answer 5

四舍五入为整数并验证：

def isRoot(n, root):
    power = int(round(math.log(n, root)))
    return root ** power == n

Is Root Algorithm