Exponenciación Rápida

¿Cómo calcular $a^n$ eficientemente para $n$ muy grande? La manera obvia de hacerlo, multiplicando a $n$ veces puede no ser suficientemente eficiente si $n$ es muy grande o tenemos que hacer muchas exponenciaciones. Hay otra forma de calcularlo que tan solo requiere $\mathcal{O}(\log n)$ multiplicaciones: Se basa en la siguiente fórmula recursiva:

\[ a^n = \begin{cases} \left(a^{\frac{n}{2}}\right)^2 & \text{si n es par} \\ \left(a^{\frac{n-1}{2}}\right)^2 \cdot a & \text{si n es impar} \end{cases} \]

En código, esto sería:

int pot(int a, int n) {
    if (n == 0) return 1;
    int x = pot(a, n/2);
    if (n % 2 == 0) return x*x;
    return x*x*a;
} 

def potencia(a, b):
	if b == 0: return 1
	s = potencia(a, b//2)
	if b%2 == 0: return s*s
	else: return s*s*a

Nótese que nos ahorramos casi la mitad de las multiplicaciones en cada paso recursivo, ya que en lugar de multiplicar por $a$ $\frac{n}{2}$ veces simplemente ponemos el resultado en una variable y la multiplicamos una vez por sí misma.

Cuando $n$ es muy grande para $a$ mayor que $1$ es posible que el resultado no quepa en las variables de números enteros de C++. Por eso, en problemas en los que hay que realizar exponenciaciones y trabajar con números muy grandes normalmente te piden que des el resultado módulo un número, es decir, que des el resto a dividir el resultado por ese número. Para implementar la exponenciación rápida en ese caso sólo hay que poner %mod en cada return, ya que al multiplicar da igual que hayas “tomado módulo” antes: Si $x$ da resto $r_x$ al dividirlo por $m$ y $y$ da resto $r_y$ al dividirlo por $m$, entonces $xy$ da el mismo resto al dividirlo por $m$ que $r_xr_y$. Se demuestra de forma sencilla: si $q_x$ y $q_y$ son los cocientes al dividir enteramente $x$ e $y$ por $m$,

\[ x =q_xm + r_x, y =q_ym + r_y \implies xy = q_xq_ym^2+q_yr_xm+q_xr_ym+r_xr_y = \]

\[ =(q_xq_ym+q_yr_x+q_xr_y)m+r_xr_y \]

Es decir, $xy$ es igual a un múltiplo de $m$ más $r_xr_y$, así que el resto al dividirlo por $m$ será el mismo que al dividir $r_xr_y$ por $m$ .

Pequeño teorema de Fermat (Sección opcional más avanzada)

En varios problemas tenemos que trabajar módulo p, donde p es un primo. En este caso, hay un teorema bastante importante relacionado con la exponenciación:

Pequeño teorema de Fermat: Sea $p$ primo y $a$ no divisible por $p$. Entonces $a^{p-1} \equiv 1 \pmod{p}$.

Demostración: Presentamos una demostración combinatórica. 

Consideremos pulseras de $p$ cuentas (bolas), con cada cuenta pintada por uno de $a$ colores. Hay un total de $a^p$ pulseras distintas: al ser $p$ primo, las únicas pulseras con simetría rotacional son las $a$ que tienen todas las cuentas del mismo color. Las otras se pueden dividir en grupos de $p$ pulseras rotacionalmente equivalentes, es decir, que son iguales si se giran.

Por tanto $a^p-a$ es divisible por $p$, y al ser $a$ no divisible por $p$, entonces $a^{p-1}-1$ es divisible por $p$. $\square$

Este teorema nos dice que para calcular $a^n \pmod{p}$, basta con calcular $a^{n \pmod{p-1}} \pmod{p}$, ya que los restos se repiten cada $p-1$ potencias. No obstante, generalmente calcular el módulo $p-1$ no merece la pena a no ser que $n$ sea mucho mayor que $p$. Sin embargo, este teorema tiene otras aplicaciones. Supongamos que queremos calcular $b$ tal que $ab \equiv 1 \pmod{p}$ ($b$ es el llamado inverso modular de $a$ y se puede demostrar que módulo $p$ primo existe y es único). La solución por fuerza bruta sería calcular $ab$ para todo $b = 1, \ldots, p-1$ en $\mathcal{O}(p)$. Por el pequeño teorema de Fermat, simplemente calculamos $b \equiv a^{p-2} \pmod{p}$, que utilizando exponenciación rápida se calcula en $\mathcal{O}(\log p)$.