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

(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)

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

ПосиланняРедагувати