Повторюване піднесення до квадрата

Повторюване піднесення до квадрата (англ. exponentiating by squaring, repeated squaring) — алгоритм, призначений для піднесення числа x до натурального степеня n за менше число множень, ніж цього вимагає визначення степені.

Алгоритм не завжди найоптимальніший: наприклад, піднесення в степінь n = 15 повторюваним піднесенням до квадрата потребує 6 множень, хоча це можна досягти за 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}.$

Приклад

Розглянемо обчислення $3^{13}$. Двійкове представлення 13 — ${(1101)}_2$, отже $8 + 4 + 1 = 13$.

$3^1$	$3$
$3^2$	$9 = 3 \times 3$
$3^4$	$81 = 9 \times 9$
$3^8$	$6561 = 81 \times 81$

Для обчислення кожного наступного рядка потрібне одне множення.

$3^1 \times 3^4 \times 3^8 = 3^{13} = 1594323$

Обчислювальна складність

Кількість множень, необхідна для піднесення числа 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ⁿ можна використовувати алгоритм повторюваного піднесення до квадрата.