1´ 23+1´ 22+0´ 21+1´ 20.
Коефіцієнти при 20, 21, 22 тощо – це послідовні остачі від ділення на 2 чисел
n, ndiv 2, (ndiv 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, ndiv 2, (ndiv 2) div 2, ((ndiv 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.