Escrito por Lúcio Cardoso
Imagine que desejamos calcular o valor , onde e são ambos números naturais. Uma possível maneira de fazer esta tarefa seria simplesmente usar a função já existente do C++. No entanto, como a complexidade desta função , precisamos de uma maneira mais esperta de calcular este valor se possuir valores muito grandes.
Descrição do Algoritmo
Nós já sabemos que . Em particular, sabemos que . Logo, se o expoente de for par, podemos dizer que . No entanto, se for ímpar, temos algo similar: podemos afirmar que .
Usando as observações acima, podemos montar a seguinte recorrência:
Assim, para calcular , podemos utilizar uma função recursiva que segue a recorrência acima.
Complexidade
Perceba que em cada momento do algoritmo, o expoente é divido por nas chamadas sucessivas da função. Logo, a complexidade do algoritmo é a mesma que a quantidade máxima de vezes que podemos dividir por tal que . Este valor é exatamente , e portanto, a complexidade da exponenciação rápida é .
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 (, ou " escolhe ") módulo um número primo (por exemplo, ) com complexidade logarítmica.
Seja o módulo que desejamos utilizar (onde é primo). Sabemos que:
, onde representa o inverso modular de .
No entanto, como é primo, sabemos, pelo Pequeno Teorema de Fermat, que se é um número natual, então o inverso multiplicativo modular de é .
Portanto, teremos que . Assim, se pré-calcularmos todos os fatoriais módulo menores ou iguais a em , conseguimos usar a exponenciação rápida para calcular inversos multiplicativos, e logo mais, calculamos em .