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)$$.