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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Повторюване піднесення до квадрата (англ. 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.

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