Как побыстрей посчитать число в большой степени? Например, 3,5 в степени 40 ?..

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера.

Язык Си
int power(int t, int k) {
// возведение t в степень k
int res = 1;
while (k) {
if (k & 1) res *= t;
t *= t;
k >>= 1;
}
return res;
}
[править] Паскаль
function power(t, k: integer): integer; //возведение числа t в степень k
var
res:integer;
begin
res := 1;
while (k > 0) do
begin
if (k mod 2 = 1) then // {или напишите "if (k and 1 = 1)" для большей скорости выполнения}
res := res * t;
t := t * t;
k := k div 2; // {или напишите "k := k shr 1;" для большей скорости выполнения}
end;
power := res;
end;
[править] Оценка сложности
Чтобы узнать, сколько умножений потребуется для возведения числа x в степень n алгоритмом быстрого возведения в степень, нужно произвести вычисления по следующей формуле: k = H + 2(E − 1), где H — количество нулей, а E — количество единиц в двоичной записи числа n.

Так, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 умножений.

Таким образом количество умножений равно O(lnn).

[править] Обобщение
Пусть пара (S, *) — полугруппа, то есть S — произвольное множество, на котором задана бинарная операция * такая, что:

Для любых элементов a и b из S справедливо: (a * b) так же из S. (замкнутость)
Для любых элементов a, b и c из S справедливо: ((a * b) * c) = (a * (b * c)). (ассоциативность)
Мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень: