Быстрое возведение в степень в Python

Web scraping с помощью Python Программирование и разработка

Мы собираемся узнать о том, как его можно оптимизировать или сделать быстрое вычисление мощности чисел по сравнению с традиционным методом с использованием Python.

Что такое экспоненциация ?

Это математическая операция, в которой мы вычисляем выражение a b , повторяя умножение a на ba несколько раз. Где «а» называется основанием, а «б» — мощностью. Давайте рассмотрим пример возведения в степень, как описано ниже:

Пример:

Предположим, нам нужно вычислить 5 4. Таким образом, 5 4 можно расширить, умножив само число 5 в 4 раза на число, указанное в надстрочном индексе (или степени), как объяснено ниже:

Base = 5, Power = 4

54 = 5*5*5*5 = 625

Быстрое возведение в степень в Python

Быстрое возведение в степень — это оптимизация традиционных методов вычисления мощностей. Оптимизацию можно выполнить, уменьшив дополнительную итерацию условного оператора цикла for. Разберемся с реализацией. Оптимизировать будем двумя способами:

  1. Используя функцию pow()из модуля Math
  2. Без использования функции pow().
  3. С помощью метода «разделяй и властвуй»

Быстрое возведение в степень с использованием функции pow()

Здесь мы вычисляем половинную мощность для метода оптимизации, например, если нам нужно вычислить 5 4, мы вычисляем 5 2. Если мощность нечетная, то одно значение умножается на оставшийся результат, чтобы получить желаемый результат.

Python3

def optimize(val, power):
    result = pow(val, power//2)
    result = result * result
    if power % 2 != :
        result = result * val
    return result
cal = optimize(2, 5)
print(cal)

Вывод:

32

Быстрое возведение в степень без использования функции pow()

В этом мы оптимизируем без использования функции степени. Если мощность положительна, это означает, что мы должны умножать ее напрямую, а если мощность отрицательна, нам придется многократно умножать 1/val. Здесь мы уменьшили количество итераций возведения в степень, чтобы оптимизировать код для больших чисел.

Читайте также:  Как использовать API с Java?

Python3

def optimize(val, power):
    result = 1
    if val == :
        return
    if power > :
        for i in range(1, (power//2)+1):
            result = result * val
        result = result * result
        if power % 2 != :
            result = result * val
    elif power < :
        for i in range(1, ((-power//2) + 1)):
            result = result * 1/val
        result = result * result
        if power % 2 != :
            result = result * 1/val
    else:
        pass
    return result
cal = optimize(2, -2)
print(cal)

Вывод:

0,25

Использование быстрого возведения в степень: метод «разделяй и властвуй»

В этом подходе мы будем делить экспоненту на подзадачу и умножать число, рекурсивно вызывая функцию.

Python3

# Function to calculate x raised to the power y in O(logn)
def power(x, y):
    temp =
    if(y == ):
        return 1
    temp = power(x, int(y / 2))
    if y % 2 == :
        return temp * temp
    else:
        return x * temp * temp
result1 = power(2, 5)
print(result1)
 
result2 = power(3, 6)
print(result2)
 
# This code is contributed by Aditya Sharma

Вывод

32
729
  • Временная сложность: O (log n)
  • Вспомогательное пространство: O (log n)

Оцените статью
bestprogrammer.ru
Добавить комментарий

Adblock
detector