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 con exponente , es decir, calcular . La forma obvia de hacerlo en programación consiste en multiplicar por si mismo unas veces con un bucle. Esta solución requiere de 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 la base y el exponente (un entero no negativo) al que queremos elevar el número . El algoritmo de exponenciación binaria nace de una simple observación: Si es par entonces , y si es impar entonces . 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 operaciones.

Bibliografía