Este dilema se puede tratar de diferentes maneras, pero en este caso te mostramos la que para nosotros es la solución más completa.
Solución:
Escribe $b = b_0 + b_1 2 + b_2 2^2 + … + b_n 2^n$ donde $b_k$ son los dígitos binarios de la representación de $b$ en base $2$. Tenga en cuenta que $n$ varía logarítmicamente con $b$. Después:
$$ a^b = a^b_0 cdot (a^2)^b_1 cdot (a^2^2)^b_2 cdot … cdot (a^2^ n)^b_n $$
Los términos donde los bits $b_k = 0$ se evalúan como $1$ y se pueden omitir. Los términos con $b_k = 1$ tienen la forma $a^2^k$ y se pueden calcular elevando repetidamente $a$ $k$ al cuadrado. Esto es precisamente lo que hace el código publicado.
El algoritmo usa la expansión binaria del exponente para reducir el número de multiplicaciones que uno tiene que hacer. Si tomas $a$ y lo elevas al cuadrado y luego lo elevas al cuadrado nuevamente y luego lo elevas al cuadrado nuevamente, generas los números $a, a^2, a^4, a^8,ldots,a^2^k$ hasta que $2^k+1>b$ sea Así que eso requiere alrededor de $log_2 b$ multiplicaciones. Entonces, si expresas $b$ en binario, por ejemplo, $b=1101001$, entonces $a^b = a^2^6+2^5+2^3+2^0 = a^2^6 a^2^5a^2^3a^2^0$, y acabas de calcular todas estas potencias de $a$, así que multiplícalas juntas y eso es aproximadamente $log_2 b$ más multiplicaciones.
valoraciones y comentarios
Si guardas algún recelo y disposición de refinar nuestro ensayo te proponemos escribir una nota y con mucho placer lo estudiaremos.