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

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

Опис

Нехай $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 множень.

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

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

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

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

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

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

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

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

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

Нехай пара (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ⁿ можна застосовувати алгоритм повторюваного піднесення до квадрата.

Посилання

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