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

Швидке піднесення до степеня — алгоритм піднесення числа 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}.$

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

$\left\{\begin{array}{c}{s}_1=x\\ s_{i+1}=s_i^2\cdot x^{m_{k-i}}\\ i=1,2,\dots ,k\end{array}\right\}.$

Приклад

Розглянемо обчислення $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)$), а ефективного алгоритму побудови найкоротшої послідовності обчислень у загальному випадку відомо не булоШаблон:Sfn.

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

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

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

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

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

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

Посилання

• Repeated Squaring Шаблон:Webarchive Шаблон:Ref-en
• Шаблон:Публікація