Exponenciação Binária

A exponenciação binária (ou exponenciação modular rápida) é um truque que permite calcular $a^n$ usando apenas $O(\log n)$ multiplicações (em vez de $O(n)$ multiplicações exigidas por uma abordagem mais forçada).

Também possui aplicações importantes em muitas tarefas não relacionadas à aritmética, uma vez que pode ser usado com qualquer operação que tenha a propriedade da associatividade:

$$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$

Isso se aplica à multiplicação modular, à multiplicação de matrizes e para outros problemas que discutiremos abaixo.

Algoritmo

Elevar $a$ ao índice $n$ é expressado como multiplicação de $a$ feita $n - 1$ vezes: $a^{n} = a \cdot a \cdot \ldots \cdot a$. Entretanto, essa abordagem não é prática com valores enormes de $a$ e $n$.

$a^{b+c} = a^b \cdot a^c$ e $a^{2b} = a^b \cdot a^b = (a^b)^2$.

A ideia da exponenciação binária é que nós dividimos o trabalho usando a representação binária do exponente.

Vamos escrever $n$ na base 2, por exemplo: $$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$

Desde que o número $n$ tenha exatamente $\lfloor \log_2 n \rfloor + 1$ digitos na base 2, nós apenas precisamos performar $O(\log n)$ multiplicações, se já soubermos as exponenciações $a^1, a^2, a^4, a^8, \dots, a^{\lfloor \log n \rfloor}$.

Portanto, precisamos apenas conhecer uma maneira rápida de calculá-los. Partimos da ideia de que um elemento na sequência é apenas o quadrado do elemento anterior.

$$\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}$$

Então para conseguir a resposta final $3^{13}$, precisamos apenas multiplicar 3 exponenciações (pulando $3^3$ pois o bit correspondente em $n$ não está definido(n = 13 = 1101)): $3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$

A complexidade final do algoritmo é $O(\log n)$: precisamos calcular $\log n$ exponenciações de $a$, e então precisamos fazer no máximo $\log n$ multiplicações para conseguir a resposta.

A seguinte abordagem recursiva expressa a mesma ideia:

$$a^n = \begin{cases} 1 &\text{se } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{se } n > 0 \text{ e } n \text{ par}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{se } n > 0 \text{ e } n \text{ impar}\\ \end{cases}$$

Implementação

Primeiro, a abordagem recursiva, que é uma tradução direta da fórmula recursiva:

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)   
        return res * res * a;
    else
        return res * res;
}

A segunda abordagem consegue completar a mesma tarefa de uma forma não recursiva. Calcula todas as exponenciações em um loop, e multiplica as potências com os correspondentes bits(se eles estiverem definidos) em $n$. Apesar da complexidade das duas serem a mesma, essa abordagem será mais rápida na prática, pois temos a sobrecarga das chamadas recursivas.

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)  //impar
            res = res * a;
        a = a * a;
        b >>= 1;  // /2
    }
    return res;
}

Aplicações

Cálculo eficaz de expoentes grandes modulo algum número

Problema: Calcule $x^n \bmod m$. Essa é uma operação bem comum. Por exemplo, é usado para calcular a multiplicação modular inversa.

Solução: Como sabemos que o operador do módulo não interfere nas multiplicações ($a \cdot b \equiv (a \bmod m) \cdot (b \bmod m) \pmod m$), podemos usar diretamente o mesmo código e apenas substituir cada multiplicação por uma multiplicação modular:

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)    //impar  (& operador bitwise and)
            res = res * a % m;  //o mesmo que (res % m) * (a % m)
        a = a * a % m;
        b >>= 1;   // /2 ( >> operador bitwise shift)
    }
    return res;
}

Nota: Se $m$ for um número primo, podemos acelerar um pouco esse algoritmo calculando $x ^ {n \mod (m-1)}$ em vez de $x ^ n$. Isto vem diretamente do pequeno teorema de Fermat (Fermat's little theorem).

Cálculo eficaz dos números de Fibonacci

Problema: Calcule o $n$-th número de Fibonacci $F_n$.

Solução: Para mais detalhes, veja o artigo números de Fibonacci. Iremos apenas apresentar uma visão geral do algoritmo. Para calcular o próximo número de Fibonacci, são necessários apenas os dois anteriores, como $F_n = F_{n-1} + F_{n-2}$. Nós podemos construir uma $2 \times 2$ matriz que descreve essa transformação: a transição de $F_i$ e $F_{i+1}$ para $F_{i+1}$ e $F_{i+2}$. Por exemplo, aplicando essa transformação ao par $F_0$ e $F_1$ iria mudar para $F_1$ e $F_2$. Portanto, podemos elevar essa matriz de transformação ao $n$-th índice para encontrar $F_n$ em tempo de complexidade $O(\log n)$.

Aplicando uma permutação $k$ vezes

Problema: É dada uma sequência de tamanho $n$. Aplique a ela uma dada permutação $k$ vezes.

Solução: Simplesmente eleve a permutação para o $k$-th índice usando exponenciação binária, e depois aplique na sequência. Isso lhe dará uma complexidade do tempo $O(n \log k)$.

Nota: Essa tarefa pode ser resolvida com mais eficiência em tempo linear, construindo o grafo de permutação e considerando cada ciclo de forma independente. Então poderia calcular $k$ modulo o tamanho do ciclo e encontrar a posição final para cada número que faz parte desse ciclo.

Aplicação rápida de um conjunto de operações geométricas a um conjunto de pontos

Problema: Dados $n$ pontos $p_i$, aplique $m$ transformações para cada um desses pontos. Cada transformação pode ser uma mudança, uma escala ou uma rotação em torno de um determinado eixo por um determinado ângulo. Também existe uma operação "loop" que aplica uma lista de transformações $k$ vezes (operações de "loop" podem ser aninhadas). Você deve aplicar todas as tranformações em $O(n \cdot t)$, onde $t$ é o número total de transformações a serem aplicadas.

Solução: Vejamos como os diferentes tipos de transformações alteram as coordenadas:

Como você pode ver, cada uma das transformações pode ser representada como uma operação linear nas coordenadas. Assim, uma transformação pode ser escrita como uma matriz $4 \times 4$ da forma:

$$\begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \\ \end{pmatrix}$$

que, quando multiplicado por um vetor com as coordenadas antigas e uma unidade, gera um novo vetor com as novas coordenadas e uma unidade:

$$\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \\ \end{pmatrix} = \begin{pmatrix} x' & y' & z' & 1 \end{pmatrix}$$

(Por que introduzir uma quarta coordenada fictícia, você pergunta? Sem isso, não seria possível implementar a operação de Mudança, pois exige que adicionássemos uma constante às coordenadas. Sem as coordenadas fictícias, poderíamos aplicar apenas uma combinação linear às coordenadas, não sendo possível adicionar uma constante.)

Aqui estão alguns exemplos de como as transformações são representadas na forma de matriz:

Agora, uma vez que cada transformação é descrita como uma matriz, a sequência de transformações pode ser descrita como um produto dessas matrizes, e um "loop" de $k$ repetições pode ser descrito como a matriz elevada ao índice $k$ (na qual pode ser calculada usando exponenciação binária $O(\log{k})$). Dessa forma, a matriz que representa todas as transformações pode ser calculada primeiro em $O(m \log{k})$, e depois pode ser aplicada para cada um dos $n$ pontos em $O(n)$ para uma complexidade total de $O(n + m \log{k})$.

Número de caminhos de tamanho $k$ em um grafo

Problema: Dado um grafo direcionado, sem pesos e com $n$ vertices, descubra o número de caminhos de tamanho $k$ de qualquer vértice $u$ para qualquer outro vértice $v$.

Solução: Esse problema é considerado em mais detalhes em um outro artigo. O algoritmo consiste em elevar a matriz de adjacência $M$ do grafo (uma matriz na qual $m_{ij} = 1$ se tiver uma aresta de $i$ para $j$, ou $0$ caso contrário) para o $k$-th índice. Agora $m_{ij}$ será o número de caminhos de comprimento $k$ de $i$ para $j$. O tempo de complexidade dessa solução é $O(n^3 \log k)$.

Nota: Nesse mesmo artigo, outra variação desse problema é considerada: quando as arestas tem peso e é requerido encontrar o caminho com menor peso contendo exatamente $k$ arestas. Como mostrado nesse artigo, esse problema também é resolvido pela exponenciação da matriz de adjacência. A matriz teria o peso da aresta de $i$ para $j$, ou $\infty$ se não existir essa aresta. Em vez da operação usual de multiplicar duas matrizes, uma modificada deve ser usada: em vez de multiplicação, os dois valores são adicionados e, em vez de um somatório, é necessário um mínimo. Isto é: $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$.

Variação da exponenciação binária: multiplicando dois números modulo $m$

Problema: Multiplique dois números $a$ e $b$ modulo $m$. Mas o produto de $a$ e $b$ é muito grande para ser armazenado em um inteiro 64-bit. A ideia é calcular $a \cdot b \pmod m$ sem usar nenhum tipo de biblioteca ou aritmética para grandes números.

Solução: Simplesmente aplicamos o algoritmo de construção binário descrito acima, realizando apenas adições em vez de multiplicações. Em outras palavras, "expandimos" a multiplicação de dois números para $O (\log m)$ operações de adição e multiplicação por dois (na qual, em essência, é uma adição).

$$a \cdot b = \begin{cases} 0 &\text{se }a = 0 \\ 2 \cdot \frac{a}{2} \cdot b &\text{se }a > 0 \text{ e }a \text{ par} \\ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{se }a > 0 \text{ e }a \text{ impar} \end{cases}$$

Nota: Você pode resolver por um caminho diferente com operações com números do tipo float. Primeiro calcule a expressão $\frac{a \cdot b}{m}$ usando números float(point-float numbers) e jogue-o em um unsigned integer(inteiro sem sinal) $q$. Subtraia $q \cdot m$ de $a \cdot b$ usando aritmética de unsigned integer e pegue o modulo $m$ para encontrar a resposta(meio confuso mas com uma boa prática em usar diferentes tipos em uma liguagem de programação você consegue pegar a prática). Essa solução parece pouco confiável, mas é muito rápida. Veja aqui para mais informações.

Problemas