Алгоритм быстрого возведения в степень

Алгоритм быстрого возведения в степень — алгоритм, предназначенный для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени.

Алгоритм не всегда оптимален: например, быстрое возведение в степень n = 15 потребует 6 умножений, хотя возведение в 15-ю степень можно выполнить и за 5 умножений.

Описание

Пусть $n=(\overline {m_{k}m_{k-1}...m_{1}m_{0}})_2$ — двоичное представление степени n, то есть,

$n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+\dots+m_{1} \cdot 2+m_{0},$

где $m_{k}=1, m_{i} \in \{ 0,1 \}$. Тогда

$x^{n}=x^{((\dots((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+\dots) \cdot 2+m_{1}) \cdot 2 + m_{0}}=((\dots(((x^{m_{k}})^{2} \cdot x^{m_{k-1}})^{2}\dots)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}.$

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

$\begin{Bmatrix} s_1=x \\ s_{i+1}=s_i^2 \cdot x^{m_{k-i}} \\ i=1,2,\dots,k \end{Bmatrix}.$

Вычислительная сложность

Количество умножений, требуемое для возведения числа x в степень n алгоритмом быстрого возведения в степень, даётся формулой: $H+2(E-1)$, где H — количество нулей, а E — количество единиц в двоичной записи числа n. Таким образом, количество умножений равно $O(\log{n})$.

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

Обобщения

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

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

Мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

$a^n=\left\{ \begin{array}{ll} a & n = 1 \\ a * \left(a^{n-1}\right) & n > 1 \end{array} \right.$

Для вычисления значений aⁿ можно использовать алгоритм быстрого возведения в степень.

Ссылки

Имеется викиучебник по теме
«Программные реализации быстрого возведения в степень»

• Валицкас А. И. Конспект лекций по дисциплине: Элементы абстрактной и компьютерной алгебры. // Тобольск, ТГПИ им. Д. И. Менделеева, 2004.