Question

Быстрое возведение в степень Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: an=(a2)n/2 при чётном n, an=a∗an−1 при нечётном n. Реализуйте алгоритм быстрого возведения в степень. Если вы всё сделаете правильно, то количество умножений будет иметь порядок log2n. Нельзя использовать операцию возведения в степень. Входные данные: Вводится действительное число a и целое неотрицательное число n. Выходные данные: Выведите ответ на задачу.
Примеры: Ввод 2 7 Вывод 128 Ввод 1.00001 100000 Вывод 2.71827



ппппппппппппппиииииииииитттттттттттоооооооооооооооннннннннн

Answer 1

Вот вариант без использования встроенных кэшей, только рекурсивная функция и словарь, всё как положено:

def pow(number, power):

   powers = {0: 1, 1: number}

   def rec(p):

       if p in powers:

           # уже вычисляли эту степень

           return powers[p]

       elif p % 2 == 0:

           # чётный случай

           result = rec(p//2) * rec(p//2)

           powers[p] = result

           return result

       else:

           # нечётный случай

           result = rec(p-1) * number

           powers[p] = result

           return result

   return rec(power)

print(pow(1.253, 25))