Exponenciación binaria: Cómo calcular rápidamente la potencia de un número

Un problema muy común es el de calcular la potencia de un número $b$ con exponente $n$, es decir, calcular $b^n$. La forma obvia de hacerlo en programación consiste en multiplicar $b$ por si mismo unas $n$ veces con un bucle. Esta solución requiere de $O(n)$ operaciones, lo que puede ser demasiado para determinados contextos. En este artículo expondré sobre una forma más eficiente de resolver el problema, aunque sólo aplica para números .

La idea

Sea $b$ la base y $n$ el exponente (un entero no negativo) al que queremos elevar el número $b$. El algoritmo de exponenciación binaria nace de una simple observación: Si $n$ es par entonces $b^n = (b^2)^{\frac{n}{2}}$, y si $e$ es impar entonces $b^n = b \times b^{n-1}$. Por lo tanto el problema se puede expresar de forma recursiva:

potencia(b, n):
    // Caso base
    Si es es nulo:
        retornar 1

    Si e es par:
        retornar potencia(b*b, n/2)
    Si e es impar:
        retornar b * potencia(b, n-1)

Complejidad temporal

La exponenciación binaria es mucho mejor que la lineal, sobretodo si se implementa de forma iterativa y usa con exponentes grandes. Se puede demostrar que ejecuta $O(\log{n})$ operaciones.

Bibliografía