如何使用 Python3 中的对数属性确保一个数是另一个数的幂？

Question

我想检查数字 x 是否是另一个数字 y 的指数幂。我懂数学：用对数。

但是，当我在 Python3 中使用 log() 函数执行此方法时，我得到了奇怪的结果。我想测试 243 是否是 3 的幂，结果是，我的代码返回了 False。我的代码如下：

power = log(n, 3)
if (int(power)) == power:
    return True

我得到 4.999999999999999 作为 power 中的结果。我在 Python3 中阅读了有关浮点数和对数的精度和其他战术细节，我尝试了这些解决方案，但其中 none 给了我我知道就基本数学而言是正确的答案.

我试过这个：

from math import log
from decimal import Decimal, Context

class Power:
    def power_func(self, n: int) -> bool:
        if n == 0:
            return False
        ctx = Context(prec=20)
        power = log(n, Decimal(3))
        if (int(power)) == power:
            return True
        return False

我想我在这里缺少 Python 的一些基础知识，但不确定如何进一步进行。我知道完成任务的其他解决方案，但我想在 Python3.

中使用对数来实现此目的

Answer 1

return 3**math.ceil(power) == n or 3**math.floor(power) == n

Answer 2

不要使用对数；他们依靠真正的算术来正确工作，这是 Python 做不到的。

相反，使用重复平方从基数接近 n。

def is_power_of(n, b):
    y = b
    # Compute y = b**2, b**4, ..., b**2**i until y reaches or exceeds n
    # i = 1
    while y < n:
        y = y * y
        # i *= 2

    # If we overshoot, divide by b until we either
    # reach n or get a non-zero remainder
    while y > n:
        y, r = divmod(y, b)
        # i -= 1
        if r:
            return False
    else:
        return y == n

请注意，如果函数 returns 为真，i 将是满足 b**i == n.

的值

Answer 3

使用来自 Previous Post

的日志

from math import log

def is_power(a, b):
  " check if a is a power of b (i.e. b is base)"
  if b == 1 or a == 0: return False
  return return b ** int(round(log(a, b))) == a


print(is_power(243, 3))  # returns True

这应该适用于实际数字

It may be worth noting that while this solution isn't totally infallible for large values, depending as it does on floating-point accuracy, a would have to be spectacularly large for that to be a problem. E.g., with b = 2, a = 2**(2**53 + 1) and IEEE 754 floats, this can't possibly work, but you'd need approximately 1.2 PB of RAM and a machine with an address space bigger than 2**48 to be able to represent that value of a in the first place. --Mark Dinkinson

Yes, there's no computer in existence with enough memory to hold integers large enough for this to plausibly fail. But I didn't mention that, because if the OP was surprised that log() may not be exact in all cases, they're not quite ready to appreciate an argument about the far-flung limits of theoretical possibilities ;-) – Tim Peters

性能

与@chepner 解决方案中使用的 is_power_of 例程等幂方法相比

for k in range(1, 300):
    num = 3**k
    assert is_power_of(num, 3) == is_power(num, 3)

There are no asserts so the two methods equal at least up till 3^300 =136891479058588375991326027382088315966463695625337436471480190078368997177499076593800206155688941388250484440597994042813512732765695774566001 (144 digits)

num = 3**300
%timeit is_power_of(num, 3)--uses powers
100000 loops, best of 3: 136 µs per loop

%timeit is_power(num, 3)--uses log
100000 loops, best of 3: 2.71 µs per loop

因此，对于大数，log 方法的速度要快 50 倍以上但是，对于较小的数字，这两种方法具有可比性

Answer 4

看起来问题坚持使用和处理 log()，但天真地不可能像@DarryIG 暗示的那样为计算机实现完美的精度。

如果没有 log()，更好的方法可能是不使用基数乘法，因为它需要大量重复计算。相反，使用除法并检查余数以更快收敛。只要y%b不是整数，我们就可以立即终止计算。

def isPower(n,b):
  y = n
  while y % b == 0: y /= b
  return y == 1

如何使用 Python3 中的对数属性确保一个数是另一个数的幂？

How do I ensure that a number is a power of another number using logarithmic property in Python3?

python

python-3.x

math

logarithm

如何使用 Python3 中的对数 属性 确保一个数是另一个数的幂？

How do I ensure that a number is a power of another number using logarithmic property in Python3?

python

python-3.x

math

logarithm

如何使用 Python3 中的对数属性确保一个数是另一个数的幂？