Instituto de Matemática - UFRGS - Mat01169 - Cálculo Numérico
Estudo 1

Avaliação de Potências Inteiras

Nosso objetivo é tratar a avaliação computacional eficiente de potências $x^n$, onde $x$ é um número real e $n$ é um número inteiro, usando somente as quatro operações algébricas fundamentais. Se $n=0$, $x^n=0$ é a resposta trivial. Por outro lado, se $n < 0$ (e, obviamente, $x \neq 0$), lembramos que $$x^n = (1/x)^{-n}$$. Dessa forma, basta considerar o caso em que $n$ é inteiro e positivo.

Estratégia 1: o algoritmo mais intuitivo para $y=x^n$

Consiste em usar multiplicações por $x$.

P1: $y \leftarrow 1.0$;

Para $k=1,2,\dots,n$ faça

P2: $y \leftarrow y \cdot x$;

Fim Para

Retorne $y$;

Essa estratégia de avaliação requer $n$ produtos ponto-flutuante.

Estratégia 2: usando a expansão binária de $n$

Consiste em varrer os algarismos binários da expansão de $n$, da direita para a esquerda, aplicando duas operações: a de multiplicar por $x$ e a de elevar ao quadrado, dependendo se o algarismo encontrado é $0$ ou $1$. Três variáveis $k$, $y$ e $z$ são usadas. O próprio algoritmo calcula a expansão binária de $n$, usando estratégia clássica de dividir por $2$ e determinar o resto.

P1: $k \leftarrow n$;

P2: $y \leftarrow 1.0$;

P3: $z \leftarrow x$;

Enquanto $k > 0$ faça

P4: $m \leftarrow k$;

P5: $k \leftarrow \lfloor k/2 \rfloor$;

P6: Se $m > 2 \cdot k$ então faça $y \leftarrow z \cdot y$;

P7: Se $k > 0$ então faça $z \leftarrow z \cdot z$;

Fim-Enquanto

Retorne $y$;

Essa estratégia de avaliação requer $\lfloor \log_2(n) \rfloor + q_n$ produtos de números reais, onde $q_n$ é o número de algarismos unitários (1) na expansão binária de $n$. No pior caso, $n = 2^p - 1$ para algum inteiro $p$, e temos $q_n = \lfloor \log_2(n) \rfloor + 1$ e assim seriam necessários $2 \lfloor \log_2(n) \rfloor + 1$ produtos reais.

Exemplo: avaliar $x^9$

$k$	$y$	$z$
9	1	$x$
4	$x$	$x^2$
2	$x$	$x^4$
1	$x$	$x^8$
0	$x^9$	$x^{8}$

e são necessários exatamente $3 + 2 = 5$ produtos.

Exemplo: avaliar $x^{15}$

$k$	$y$	$z$
15	1	$x$
7	$x$	$x^2$
3	$x^3$	$x^4$
1	$x^7$	$x^8$
0	$x^{15}$	$x^{8}$

e são necessários exatamente $2(3) + 1 = 7$ produtos.

Referências:

[1] https://en.wikipedia.org/wiki/Exponentiation_by_squaring

[2] D. E. Knuth. Seminumerical Algorithms, vol. 2 of The Art of Computer Programming, ssec 4.6.3, 3rd edition. Addison-Wesley, 1998.