Exponenciação Rápida: Descrição indutiva e implementação em Java

Neste post, apresentaremos uma implementação eficiente para o problema da exponenciação. Faremos a descrição indutiva do problema e em seguida implementaremos uma solução em Java. No  post anterior (ver post), utilizamos a indução fraca, agora vamos usar a indução forte para descrever o mesmo problema. Para revisar os conceitos básicos referentes ao uso da indução matemática na construção de algoritmos, veja o post: Indução Matemática - Visão Geral.

Matematicamente, temos o seguinte:

                                                                  $a^n = (a^{\frac{n}{2}})^2$     , se n for par
                                                                  $a^n = a * a^{n-1}$ , se n for ímpar

Descrição indutiva:

• Caso Base: Para n = 0, temos que $a^0 = 1$.
• Hipótese de Indução: Vamos assumir que temos o valor de $a^{\frac{n}{2}}$.
• Caso Geral: Simples, basta elevar ao quadrado o resultado encontrado na hipótese de indução.

A implementação em Java (ou sua linguagem predileta) segue exatamente a descrição indutiva do problema.

• Implementação em Java:

public class Potenciacao {

  public static int fastExp(int base, int exp) {
    if (exp == 0)
      return 1;
    else if (exp % 2 == 0)
      return (int) Math.pow(fastExp(base, exp / 2), 2);
    else
      return (int) (Math.pow(fastExp(base, exp - 1), 2) * base);
  }

  public static void main(String[] args) {
    System.out.println(fastExp(2, 3));
  }
}

Complexidade

A solução apresentada acima é mais eficiente que a solução utilizada no post anterior. A relação de recorrência $T(n) = T(\frac{n}{2}) + 1$ mostra que o algoritmo possui complexidade O(log n).

@inductioncode