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

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

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

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

де . Тоді

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

Приклад

[ред. | ред. код]

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

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

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

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

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

[ред. | ред. код]

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

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

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

[ред. | ред. код]

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

Однак найоптимальніший шлях має таку ж оцінку складності, як і повторюване піднесення до квадрата (), а ефективного алгоритму побудови найкоротшої послідовності обчислень у загальному випадку відомо не було[1].

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

[ред. | ред. код]

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

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

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

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

Джерела

[ред. | ред. код]
  1. Гашков, 2011, с. 142.

Посилання

[ред. | ред. код]