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