ALGORITHMS
Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в n-ую степень за O(log n) умножений (вместо n умножений при обычном подходе).
Более того, описываемый здесь приём применим к любой ассоциативной операции, а не только к умножению чисел. Напомним, операция называется ассоциативной, если для любых a, b, c выполняется:
(a * b) * c = a * (b * c)
Наиболее очевидное обобщение — на остатки по некоторому модулю (очевидно, ассоциативность сохраняется). Следующим по "популярности" является обобщение на произведение матриц (его ассоциативность общеизвестна).
Алгоритм
Заметим, что для любого числа a и чётного числа n выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
a^n = (a^{n/2})^2 = a^{n/2} * a^{n/2}
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного n мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень n нечётна. Здесь мы поступаем очень просто: перейдём к степени n-1, которая будет уже чётной:
Осталось понять, что делать, если степень n нечётна. Здесь мы поступаем очень просто: перейдём к степени n-1, которая будет уже чётной:
a^n = a^{n-1} * a
Итак, мы фактически нашли рекуррентную формулу: от степени n мы переходим, если она чётна, к n/2, а иначе — к n-1. Понятно, что всего будет не более 2 log n переходов, прежде чем мы придём к n = 0 (базе рекуррентной формулы). Таким образом, мы получили алгоритм, работающий за O (log n) умножений.
Реализация
Простейшая рекурсивная реализация:
int binpow (int a, int n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return binpow (a, n-1) * a;
else {
int b = binpow (a, n/2);
return b * b;
}
}Нерекурсивная реализация, также оптимизированная (деления на 2 заменены битовыми операциями):
int binpow (int a, int n) {
int res = 1;
while (n)
if (n & 1) {
res *= a;
--n;
}
else {
a *= a;
n >>= 1;
}
return res;
}Эту реализацию можно ещё несколько упростить, заметив, что возведение a в квадрат осуществляется всегда, независимо от того, сработало условие нечётности n или нет:
int binpow (int a, int n) {
int res = 1;
while (n) {
if (n & 1)
res *= a;
a *= a;
n >>= 1;
}
return res;
}
Ред. ScorpioT1000
Чтобы быстрее работало.