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

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

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

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

Пример:

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

Base = 5, Power = 4

5⁴ = 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 != 0:

        result = result * val

    return result

cal = optimize(2, 5)

print(cal)

Вывод:

32

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

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

Python3

def optimize(val, power):

    result = 1

    if val == 0:

        return 0

    if power > 0:

        for i in range(1, (power//2)+1):

            result = result * val

        result = result * result

        if power % 2 != 0:

            result = result * val

    elif power < 0:

        for i in range(1, ((-power//2) + 1)):

            result = result * 1/val

        result = result * result

        if power % 2 != 0:

            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 = 0

    if(y == 0):

        return 1

    temp = power(x, int(y / 2))

    if y % 2 == 0:

        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)