← Static tasks

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

emaxx algorithm

#algorithm#emaxx#math#number-theory#search

Task

Источник: e-maxx.ru/algo, страница PDF 10.

Бинарное (двоичное) возведение в степень — это приём, позволяющий возводить любое число в

-ую степень

за

умножений (вместо

умножений при обычном подходе). Более того, описываемый здесь приём применим к любой ассоциативной операции, а не только к умножению чисел. Напомним, операция называется ассоциативной, если для любых выполняется: Наиболее очевидное обобщение — на остатки по некоторому модулю (очевидно, ассоциативность сохраняется). Следующим по "популярности" является обобщение на произведение матриц (его ассоциативность общеизвестна).

Алгоритм

Заметим, что для любого числа

и чётного числа

выполнимо очевидное тождество (следующее из

ассоциативности операции умножения): Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного

мы показали,

как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.

Осталось понять, что делать, если степень

нечётна. Здесь мы поступаем очень просто: перейдём к степени

, которая будет уже чётной:

Итак, мы фактически нашли рекуррентную формулу: от степени

мы переходим, если она чётна, к

, а иначе —

к

. Понятно, что всего будет не более

переходов, прежде чем мы придём к

(базе

рекуррентной формулы). Таким образом, мы получили алгоритм, работающий за умножений.

Реализация

Простейшая рекурсивная реализация:

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;

} Эту реализацию можно ещё несколько упростить, заметив, что возведение

в квадрат осуществляется

всегда, независимо от того, сработало условие нечётности

или нет:

int binpow (int a, int n) {
int res = 1;
while (n) {
if (n & 1)

res *= a;

a *= a;

n >>= 1;

}

return res;

} Наконец, стоит отметить, что бинарное возведение в степень уже реализовано в языке Java, но только для класса длинной арифметики BigInteger (функция pow этого класса работает именно по алгоритму бинарного возведения).

C# solution

auto-draft, review before submit
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    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;
            }
    }
    int binpow (int a, int n) {
            int res = 1;
            while (n)
                    if (n & 1) {
                            res *= a;
                            --n;
                    }
                    else {
                            a *= a;
                            n >>= 1;
                    }
            return res;
    }
    int binpow (int a, int n) {
            int res = 1;
            while (n) {
                    if (n & 1)
                            res *= a;
                    a *= a;
                    n >>= 1;
            }
            return res;
    }
}

C++ solution

matched/original
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;
        }
}
int binpow (int a, int n) {
        int res = 1;
        while (n)
                if (n & 1) {
                        res *= a;
                        --n;
                }
                else {
                        a *= a;
                        n >>= 1;
                }
        return res;
}
int binpow (int a, int n) {
        int res = 1;
        while (n) {
                if (n & 1)
                        res *= a;
                a *= a;
                n >>= 1;
        }
        return res;
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    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;
            }
    }
    int binpow (int a, int n) {
            int res = 1;
            while (n)
                    if (n & 1) {
                            res *= a;
                            --n;
                    }
                    else {
                            a *= a;
                            n >>= 1;
                    }
            return res;
    }
    int binpow (int a, int n) {
            int res = 1;
            while (n) {
                    if (n & 1)
                            res *= a;
                    a *= a;
                    n >>= 1;
            }
            return res;
    }
}

Explanation

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.