Побудуємо нерекурсивний аналог наведеного алгоритму. Подамо обчислення за рекурсивним алгоритмом у такому вигляді:

x13 = (x6)2? x1 = ((x3)2? x0)2? x1 = (((x1)2? x1)2? x0)2? x1

Цьому відповідає така обробка показників степенів, що обчислюються:

13 = 6? 2+1 = (3? 2+0)? 2+1 = ((1? 2+1)? 2+0)? 2+1.

Як бачимо, обчисленню степенів відповідає обчислення значення 13, поданого поліномом відносно 2. Коефіцієнтами його є цифри двійкового розкладу числа 13. Неважко переконатися, що обчисленню степеня з довільним показником n так само відповідає обчислення n, представленого двійковим розкладом. Причому цей розклад-поліном записано за схемою Горнера. Розкриємо дужки в ньому:

1? 23+1? 22+0? 21+1? 20.

Коефіцієнти при 20, 21, 22 тощо – це послідовні остачі від ділення на 2 чисел

n, n div 2, (n div 2) div 2 тощо,

причому остачі 1 відповідає в рекурсивному алгоритмі присвоювання t:=x, а 0 – присвоювання t:=1. Таким чином, двійковий розклад, наприклад, числа 13 по степенях двійки відповідає такому поданню x13: x23? x22? 1? x20.

Отже, достатньо обчислювати степені

x20=x, x21=x2, x22=(x2)2, x23=(x22)2 тощо

та відповідні їм остачі від ділення на 2 показників

n, n div 2, (n div 2) div 2, ((n div 2) div 2) div 2 тощо,

накопичуючи в добутку лише ті двійкові степені, які відповідають остачам 1. У наступному алгоритмі добуток степенів накопичується в змінній t, а двійкові степені – в змінній x:

function pow(x, n : integer) : integer;

var t : integer; notfin : boolean;

begin

t:=1; notfin:=true;

while notfin do

begin

if odd(n) then t:=t*x;

n:=n div 2;

if n>0 then x:=x*x else notfin:=false

end;

pow:=t

end;

Задача

11. Імітувати виконання виклику функції pow (обидва варіанти) з аргументами x=2, n=11. Указати загальну кількість виконуваних арифметичних операцій при n = 5, 10, 15, 16, 1000, 1023, 1024.