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

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

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

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

Опис[ред.ред. код]

Нехай двійкове представлення степеня n, тобто,

де . Тоді

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

Приклад[ред.ред. код]

Розглянемо обчислення . Двійкове представлення 13 — , отже .

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

Обчислювальна складність[ред.ред. код]

Кількість множень, необхідна для піднесення числа x до степеня n алгоритмом, отримується за формулою: , де H — кількість нулів, а E — кількість одиниць в двійковому записі числа n. Таким чином, кількість множень дорівнює .

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

Узагальнення[ред.ред. код]

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

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

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

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

Посилання[ред.ред. код]