Что такое «бинарное возведение в степень»?

Question

[kate]

В интернете видела только непонятные примеры кода, прошу на словах объяснить, или на примере.

Comments

[Lynn «Кофеман»]

В смысле википедию пересказать?

[Antonio Solo]

2**4 = 2*2*2*2 = 16 обычное
2**4 = (2**(4/2)) * (2**(4/2)) = (2**2) * (2**2) = 4 * 4 = 16 - бинарное

Answer 1

[alex_ak1]

r := 1;
while (pow > 0) do
if (pow mod 2 = 1) then
begin
r := r * a;
pow := pow-1;
end
else
begin
r := r * r;
pow := pow div 2;
end;
Таким образом возведение в степень занимает чуть больше, чем ln2(pow) действий, а не pow действий.