Задача № 25. Вычислить xn по алгоритму быстрого возведения в степень

Формулировка. Даны натуральные числа x и n. Вычислить xⁿ, используя алгоритм быстрого возведения в степень:

Решение. Разберем этот пока неясный алгоритм, представленный в нашей задаче лишь единственной формулой. Легко понять, что указанное равенство имеет место: например, 3⁴ = 3^{4 div 2} = (3²)² = 9² = 81. Другой пример: 4⁵ = 4 * (4²)^{5 div 2} = 4 * (4²)² = 4 * 16² = 4 * 256 = 1024. Причем если выражение со степенью нельзя в один шаг преобразовать таким образом, то необходимо продолжить преобразование выражения вплоть до получения конечного ответа. Однако как теперь реализовать эту схему?

Рассмотрим пример немного сложнее. Вычислим 4⁷ = 4 * (4²)³ = 4 * (16)³ = 4 * 16 * (16²)¹ = 4 * 16 * 256 = 16384. Стоит обратить внимание на то, что на каждом шаге при вычислении изменяется только единственное обрабатывающееся число, а остальные множители выносятся однократно и необходимы только для получения ответа в последнем действии.

Чтобы исключить их из рассмотрения, при нечетном текущем числе n мы будем домножать на них некоторую промежуточную переменную r, поначалу равную 1 (кстати, нечетность числа в Pascal определяет функция odd), затем (уже независимо от условий) возведем в квадрат текущее x и разделим n на 2 с отбрасыванием остатка. При повторении этих действий на некотором шаге n обязательно станет равным 1. Это происходит потому, что деление любого нечетного числа a на 2 с отбрасыванием остатка равносильно делению на двойку числа (a – 1), которое является четным, и при делении, двигаясь по цепочке четных чисел, мы всегда придем к единице. Условие n = 1 и будет окончанием цикла с предусловием. По выходе из цикла необходимо будет в качестве ответа вывести последнее значение x, умноженное на r.

Теперь алгоритм на естественном языке:

1) Ввод x и n;

2) Присваивание переменной r числа 1;

5) Запуск цикла с предусловием n < > 1. В цикле:

1. Если n нечетно, домножаем r на x;

2. Переменной x присваиваем значение x * x;

3. Переменной n присваиваем результат от деления этой переменной на 2 с отбрасыванием остатка;

3) Вывод выражения x * r.

Код:

Из анализа данного алгоритма известно, что его асимптотическая сложность порядка O(log₂n).