При возведении целого числа в неотрицательную степень обычно используют определение степени, т.е. в цикле многократно умножают число на себя. Однако для длинных чисел этот алгоритм не является эффективным. Поэтому целесообразно использовать алгоритмы меньшей сложности, например, описаный ниже.

(Из книги А. Шеня "Программирование: теоремы и задачи".) Дано целое число а и целое неотрицательное число n. Вычислить а в степени n. Другими словами, необходимо составить программу, при исполнении которой значения переменных а и n не меняются, а значение некоторой другой переменной (например, b) становится равным а в степени n. (При этом разрешается использовать и другие переменные.) Требуется, чтобы число действий (выполняемых операторов присваивания) было порядка log₂ n (то есть не превосходило бы C * log₂ n для некоторой константы C; log₂ n — это степень, в которую нужно возвести 2, чтобы получить n).

		k := n; b := 1; c := a;
		{a в степени n = b * (c в степени k)}
		while k <> 0 do
		begin
			if k mod 2 = 0
			then begin
				k := k div 2;
				c := c * c
			     end
			else begin
				k := k - 1;
				b := b * c
			     end
		end;

Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечетно, то после вычитания единицы становится четным), так что за два цикла величина k уменьшается по крайней мере вдвое.

---

---