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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм быстрого возведения в степень — алгоритм, предназначенный для возведения числа 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.

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]