Вычислить xв степени n по алгоритму быстрого возведения в степень

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

pascal25

Решение. Разберем этот пока неясный алгоритм, представленный в нашей задаче лишь единственной формулой. Легко понять, что указанное равенство имеет место: например, 34 = 34 div 2 = (32)2 = 92 = 81. Другой пример: 45 = 4 * (42)5 div 2 = 4 * (42)2 = 4 * 162 = 4 * 256 = 1024. Причем если выражение со степенью нельзя в один шаг преобразовать таким образом, то необходимо продолжить преобразование выражения вплоть до получения конечного ответа. Однако как теперь реализовать эту схему?

Рассмотрим пример немного сложнее. Вычислим 47 = 4 * (42)3 = 4 * (16)3 = 4 * 16 * (162)1 = 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.

Код:

  1. program FastExponentiation;
  2. var
  3. x, n, r: word;
  4. begin
  5. readln(x, n);
  6. r := 1;
  7. while n <> 1 do begin
  8. if odd(n) then r := r * x;
  9. x := x * x;
  10. n := n div 2
  11. end;
  12. writeln(x * r)
  13. end.

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