Бинарное возведение в степень

Материал из Algocode wiki
Версия от 15:28, 9 октября 2019; Gutrov Egor (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Бинарное возведение в степень

Идея

Заметим, что возвести число $a$ в степень $p$ можно быстрее, чем за $p - 1$ умножение. Мы будем пользоваться следующим соображением:

Если $p = 2q$, то $a^p = a^{2q} = \left(a^q\right)^2$. Значит, нам достаточно посчитать $a^q$, чтобы посчитать $a^p$. Если $p = 2q + 1$, то просто посчитаем $a^{2q}$ и умножим на $a$.

Реализация

Сразу напрашивается рекурсивная реализация этого алгоритма:

 1 int binPow(int a, int p) {
 2     if (p == 0) {
 3         return 1;
 4     }
 5     int aq = binPow(a, p / 2);
 6     aq *= aq;
 7     if (p % 2 == 1) {
 8         aq *= p;
 9     }
10     return aq;
11 }

Эта реализация - рекурсивная, что работает долго. Поэтому стоит использовать нерекурисвную.

Опять рассмотрим двоичное представление числа $p$. Заведем текущую степень числа $a$ - $a^t$. При проходе от младших разрядов к старшим будем возводить текущую степень в квадрат, то есть $t$ увеличивается на каждом шаге в два раза. Если бит в текущем разряде выставлен бит, то умножим набираемый ответ на текущую степень.

 1 int fastBinPow(int a, int p) {
 2     int cur = a;
 3     int ans = 1;
 4     while (p > 0) {
 5         if (p & 1) {
 6             ans *= cur;
 7         }
 8         p /= 2;
 9         cur *= cur;
10     }
11     return ans;
12 }

Асимптотика

В каждом из двух случаев делалось столько итераций цикла или вызовов, сколько в числе бит, то есть все работает за $O(\log n)$ при условии, что умножение работает за $O(1)$.



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko