Швидке піднесення до степеня

Швидке піднесення до степеня — алгоритм піднесення числа x до натурального степеня n шляхом повторюваного зведення в квадрат та множення. Потребує суттєво меншої кількості множень — ${\displaystyle O(\log {n})}$ —, ніж виконання цієї операції за безпосереднім визначенням степеня — ${\displaystyle O(n)}$.

Опис

Нехай ${\displaystyle n=({\overline {m_{k}m_{k-1}...m_{1}m_{0}}})_{2}}$ — двійкове представлення степеня n, тобто,

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

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

${\displaystyle 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}}.}$

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

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

Приклад

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

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

Для обчислення кожного рядка починаючи з другого потрібне одне множення (загалом — три операції множення).

Ще дві операції множення потрібні для обчислення остаточного результату:

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

Загалом виходить п'ять множень (замість дванадцяти множень за безпосереднім визначенням степеня).

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

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

Наприклад, для піднесення до сотого степеня за цим алгоритмом потрібно лише 8 множень.

Оптимальність

Алгоритм не завжди найоптимальніший за кількістю множень: наприклад, піднесення до степеня n = 15 повторюваним піднесенням до квадрата потребує 6 множень, хоча результату можна досягти за 5:

${\displaystyle x^{2}=x\times x}$

${\displaystyle x^{3}=x^{2}\times x}$

${\displaystyle x^{6}=x^{3}\times x^{3}}$

${\displaystyle x^{12}=x^{6}\times x^{6}}$

${\displaystyle x^{15}=x^{12}\times x^{3}}$

Однак найоптимальніший шлях має таку ж оцінку складності, як і повторюване піднесення до квадрата (${\displaystyle O(\log {n})}$), а ефективного алгоритму побудови найкоротшої послідовності обчислень у загальному випадку відомо не було.

Узагальнення

Нехай пара (S, *) — напівгрупа, тобто є S — довільна множина, на якій завдана двомісна операція * така, що:

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

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

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

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

Джерела

1. Гашков, 2011, с. 142.

Посилання

• Repeated Squaring [ 20 листопада 2015 у Wayback Machine.] (англ.)
• Гашков, С. Б. . Задача об аддитивных цепочках и ее обобщения // Математическое просвещение. — 2011. — Вип. 15. — С. 138-153. — .