Бинарное возведение в степень
Бинарное возведение в степень
Идея
Заметим, что возвести число $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