Exponenciación binaria

La exponenciación binaria es un algoritmo utilizado para calcular de forma rápida grandes potencias enteras de un número dado. También es conocido como potenciación por cuadrados o elevar al cuadrado y multiplicar. Implícitamente utiliza la expansión binaria del exponente. Es de uso bastante regular en aritmética modular. Este algoritmo es similar al de la duplicación en la multiplicación.

Versión recurrente

Fundamentos

El algoritmo está basado en las siguientes tres propiedades de la potencia:

( 1)

( 2)

( 3)

Usando y en la ecuación (2) se sigue que . Tomando y en la ecuación (3) se obtiene que .

Algoritmo

El siguiente algoritmo recursivo calcula para un natural dado:

Comparado con el método original de multiplicar por sí mismo veces, este algoritmo sólo utiliza O(log n) multiplicaciones y acelera el cálculo de tremendamente; más o menos de la misma forma que el algoritmo de la multiplicación acelera una multiplicación sobre el método más lento de realizar una suma repetida.

Other Languages