Как мне убедиться, что число является степенью другого числа, используя логарифмическое свойство в Python3? - PullRequest
Новая
       17

Как мне убедиться, что число является степенью другого числа, используя логарифмическое свойство в Python3?

0 голосов
/ 17 октября 2019

Я хочу проверить, является ли число х экспоненциальной степенью другого числа, у. Я понимаю математику: используйте логарифмы.

Однако, когда я применил этот подход в Python3, используя функцию log (), я получил странные результаты. Я хотел проверить, является ли 243 степенью 3, и мой код вернул значение False. Мой код выглядит следующим образом: 

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

Я получаю 4.999999999999999 в результате в power. Я читал о точности и других тактических деталях, относящихся к числам с плавающей запятой и логарифмам в Python3, и я попробовал эти решения, но ни один из них не дал мне ответа, который, как я знаю, является правильным в отношении базовых математических вычислений.

Iпопробовал это: 

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.

Ответы [ 4 ]

2 голосов
/ 17 октября 2019

Не используйте логарифмы;они полагаются на реальную арифметику для правильной работы, что 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

Обратите внимание, что если функция возвращает true, i будет таким значением, что b**i == n.

2 голосов
/ 17 октября 2019

Использование журнала от Предыдущий пост 

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

Это должно работать для практических чисел

Возможно, стоит отметить, чтоХотя это решение не является полностью непогрешимым для больших значений, в зависимости от точности с плавающей точкой, оно должно быть невероятно большим, чтобы это стало проблемой. Например, при значениях b = 2, a = 2**(2**53 + 1) и IEEE 754 это не может работать, но вам потребуется приблизительно 1,2 ПБ ОЗУ и машина с адресным пространством, большим 2**48, чтобы иметь возможность представлять это значение впервое место. - Марк Динкинсон

Да, не существует компьютера с достаточным объемом памяти для хранения целых чисел, достаточно больших, чтобы это могло привести к ошибкам. Но я не упомянул об этом, потому что, если ОП удивился, что log () может быть не точным во всех случаях, они не совсем готовы оценить аргумент о широких пределах теоретических возможностей ;-) - ТимPeters

Производительность

По сравнению с методами полномочий, такими как процедура is_power_of, используемая в решении @chepner 

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

Утверждений нет, поэтомуэти два метода равна по крайней мере, до сих 3 ^ 300 = 136891479058588375991326027382088315966463695625337436471480190078368997177499076593800206155688941388250484440597994042813512732765695774566001 (144 цифр) 

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

Таким образом, метод журнала составляет более 50X быстрее для больших количествах, однако, эти два метода сопоставимы для меньших чисел

1 голос
/ 17 октября 2019 
return 3**math.ceil(power) == n or 3**math.floor(power) == n
0 голосов
/ 17 октября 2019

Кажется, что вопрос настаивает на использовании и обработке log (), но наивно невозможно достичь идеальной точности для компьютера, как подразумевается @DarryIG.

Без log (), лучший подход, вероятно, не используетумножение от базового числа, так как потребуется много повторных расчетов. Вместо этого идите с делением и проверьте остаток для более быстрой конвергенции. Пока y% b не является целым числом, мы можем немедленно прекратить вычисление. 

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