Matemática Computacional 04 - Exponenciação Rápida

Escrito por Lúcio Cardoso

Imagine que desejamos calcular o valor $x^n$, onde $x$ e $n$ são ambos números naturais. Uma possível maneira de fazer esta tarefa seria simplesmente usar a função já existente $pow(x, n)$ do C++. No entanto, como a complexidade desta função $O(n)$, precisamos de uma maneira mais esperta de calcular este valor se $n$ possuir valores muito grandes.

Descrição do Algoritmo

Nós já sabemos que $x^a \cdot x^b = x^{a+b}$. Em particular, sabemos que $x^2b = x^b \cdot x^b$. Logo, se o expoente $n$ de $x^n$ for par, podemos dizer que $x^n = x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}$. No entanto, se $n$ for ímpar, temos algo similar: podemos afirmar que $x^n = x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} \cdot x$.

Usando as observações acima, podemos montar a seguinte recorrência:

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

Assim, para calcular $x^n$, podemos utilizar uma função recursiva $Exp(x, n)$ que segue a recorrência acima.

Complexidade

Perceba que em cada momento do algoritmo, o expoente $n$ é divido por $2$ nas chamadas sucessivas da função. Logo, a complexidade do algoritmo é a mesma que a quantidade máxima de vezes que podemos dividir $n$ por $2$ tal que $n > 0$. Este valor é exatamente $\log_{} n$, e portanto, a complexidade da exponenciação rápida é $O(\log_{} n)$.

Segue o código abaixo para melhor entendimento:

Aplicação importante: Coeficientes Binomiais

Uma das aplicações interessantes da exponenciação rápida é a de calcular coeficientes binomiais ($a \choose b$, ou "$a$ escolhe $b$") módulo um número primo (por exemplo, $10^9 + 7$ ) com complexidade logarítmica.

Seja $P$ o módulo que desejamos utilizar (onde $P$ é primo). Sabemos que:

${a \choose b} \; (mod \; P) = \frac{a!}{b! \cdot (a-b)!} \; (mod \; P) \implies {a \choose b} \; (mod \; P) = a! \cdot inv(b! \cdot (a-b)!) \; (mod \; P)$, onde $inv(x)$ representa o inverso modular de $x$.

No entanto, como $P$ é primo, sabemos, pelo Pequeno Teorema de Fermat, que se $a$ é um número natual, então $a^{P-1} \equiv 1 \; (mod \; P) \implies a \cdot a^{P-2} \equiv 1 \; (mod \; P) \implies$ o inverso multiplicativo modular de $a$ é $a^{P-2}$.

Portanto, teremos que $inv(b! \cdot (a-b)!) = (b! \cdot (a-b)!)^{(P-2)}$. Assim, se pré-calcularmos todos os fatoriais módulo $P$ menores ou iguais a $a$ em $O(a)$, conseguimos usar a exponenciação rápida para calcular inversos multiplicativos, e logo mais, calculamos ${a \choose b} \; (mod \; P)$ em $O(\log_{} P)$.