Exponenciación binaria

La exponenciación binaria (también conocida como exponentiation by squaring) es un truco que permite calcular $a^n$ , donde $n$ es un entero no negativo, usando solo $O(\log n)$ multiplicaciones (en lugar de las $O(n)$ multiplicaciones que exige el enfoque ingenuo).

También tiene aplicaciones importantes en muchas tareas que no son aritméticas, ya que se puede usar con cualquier operación que tenga la propiedad de asociatividad:

$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$

Lo más evidente es que esto aplica a la multiplicación modular, a la multiplicación de matrices y a otros problemas que discutiremos más abajo.

Algoritmo

Elevar $a$ a la potencia $n$ se expresa de forma ingenua como multiplicar por $a$ un total de $n - 1$ veces: $a^{n} = a \cdot a \cdot \ldots \cdot a$ . Sin embargo, este enfoque no es práctico para $a$ o $n$ grandes.

$a^{b+c} = a^b \cdot a^c$ y $a^{2b} = a^b \cdot a^b = (a^b)^2$ .

La idea de la exponenciación binaria es partir el trabajo usando la representación binaria del exponente.

Escribamos $n$ en base 2, por ejemplo:

$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$

Como el número $n$ tiene exactamente $\lfloor \log_2 n \rfloor + 1$ dígitos en base 2, solo necesitamos hacer $O(\log n)$ multiplicaciones, si conocemos las potencias $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$ .

Así que solo necesitamos una forma rápida de calcularlas. Por suerte es muy fácil, porque un elemento de la secuencia es simplemente el cuadrado del anterior.

$\begin{aligned} 3^{1} & = 3 \\ 3^{2} & = {(3^{1})}^{2} = 3^{2} = 9 \\ 3^{4} & = {(3^{2})}^{2} = 9^{2} = 81 \\ 3^{8} & = {(3^{4})}^{2} = 81^{2} = 6561 \end{aligned}$

Entonces, para obtener la respuesta final de $3^{13}$ , solo hay que multiplicar tres de ellas (saltando $3^2$ porque el bit correspondiente de $n$ no está prendido): $3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$

La complejidad final de este algoritmo es $O(\log n)$ : hay que calcular $\log n$ potencias de $a$ , y luego hacer a lo sumo $\log n$ multiplicaciones para armar la respuesta final.

El siguiente enfoque recursivo expresa la misma idea:

$a^n =$

Implementación

Primero el enfoque recursivo, que es una traducción directa de la fórmula recursiva:


long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

El segundo enfoque resuelve la misma tarea sin recursión. Calcula todas las potencias en un bucle y multiplica las que corresponden a un bit prendido en $n$ . Aunque la complejidad de ambos enfoques es idéntica, este suele ser más rápido en la práctica porque no tiene el overhead de las llamadas recursivas.


long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Aplicaciones

Cálculo eficiente de exponentes grandes módulo un número

Problema: Calcular $x^n \bmod m$ . Esta es una operación muy común. Por ejemplo se usa al calcular el inverso multiplicativo modular.

Solución: Como sabemos que el operador módulo no interfiere con las multiplicaciones ( $a \cdot b \equiv (a \bmod m) \cdot (b \bmod m) \pmod m$ ), podemos usar el mismo código y simplemente reemplazar cada multiplicación por una multiplicación modular:


long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Nota: Es posible acelerar este algoritmo cuando $b >> m$ . Si $m$ es un número positivo y $\gcd(x, m) = 1$ , entonces $x^n \equiv x^{n \bmod (m-1)} \pmod{m}$ para $m$ primo, y $x^n \equiv x^{n \bmod{\phi(m)}} \pmod{m}$ para $m$ compuesto. Esto sigue directamente del pequeño teorema de Fermat y del teorema de Euler; ver el artículo sobre inversos modulares para más detalles.

Cálculo eficiente de números de Fibonacci

Problema: Calcular el $n$ -ésimo número de Fibonacci $F_n$ .

Solución: Para más detalles, ver el artículo de números de Fibonacci. Acá solo damos un panorama del algoritmo. Para calcular el siguiente número de Fibonacci solo hacen falta los dos anteriores, ya que $F_n = F_{n-1} + F_{n-2}$ . Podemos construir una matriz $2 \times 2$ que describe esta transformación: el paso de $F_i$ y $F_{i+1}$ a $F_{i+1}$ y $F_{i+2}$ . Por ejemplo, aplicar esta transformación al par $F_0$ y $F_1$ lo convierte en $F_1$ y $F_2$ . Por lo tanto, podemos elevar esta matriz de transición a la $n$ -ésima potencia para encontrar $F_n$ en complejidad temporal $O(\log n)$ .

Aplicar una permutación veces { data-toc-label=‘Applying a permutation $k$ times’ }

Problema: Se da una secuencia de longitud $n$ . Aplicarle una permutación dada $k$ veces.

Solución: Simplemente elevar la permutación a la $k$ -ésima potencia usando exponenciación binaria, y después aplicarla a la secuencia. Esto da una complejidad temporal de $O(n \log k)$ .


vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}
 
vector<int> permute(vector<int> sequence, vector<int> permutation, long long k) {
    while (k > 0) {
        if (k & 1) {
            sequence = applyPermutation(sequence, permutation);
        }
        permutation = applyPermutation(permutation, permutation);
        k >>= 1;
    }
    return sequence;
}

Nota: Esta tarea se puede resolver de forma más eficiente en tiempo lineal construyendo el grafo de la permutación y considerando cada ciclo por separado. Después se puede calcular $k$ módulo el tamaño del ciclo y encontrar la posición final de cada número que pertenece a ese ciclo.

Aplicación rápida de un conjunto de operaciones geométricas a un conjunto de puntos

Problema: Dados $n$ puntos $p_i$ , aplicar $m$ transformaciones a cada uno de esos puntos. Cada transformación puede ser una traslación, un escalado o una rotación alrededor de un eje dado por un ángulo dado. También hay una operación de “loop” que aplica una lista dada de transformaciones $k$ veces (las operaciones “loop” pueden anidarse). Hay que aplicar todas las transformaciones más rápido que $O(n \cdot length)$ , donde $length$ es el número total de transformaciones a aplicar (después de desenrollar las operaciones “loop”).

Solución: Veamos cómo cambian las coordenadas los distintos tipos de transformaciones:

Traslación: suma una constante distinta a cada una de las coordenadas.
Escalado: multiplica cada una de las coordenadas por una constante distinta.
Rotación: la transformación es más complicada (no entramos en detalles acá), pero cada una de las coordenadas nuevas todavía se puede representar como combinación lineal de las viejas.

Como se ve, cada transformación se puede representar como una operación lineal sobre las coordenadas. Así, una transformación se puede escribir como una matriz $4 \times 4$ de la forma:

$(\begin{array}{cccc} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{array})$

que, al multiplicarse por un vector con las coordenadas viejas y un uno, da un vector nuevo con las coordenadas nuevas y un uno:

$(\begin{array}{cccc} x & y & z & 1 \end{array}) \cdot (\begin{array}{cccc} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{array}) = (\begin{array}{cccc} x^{'} & y^{'} & z^{'} & 1 \end{array})$

(¿Por qué introducir una cuarta coordenada ficticia? Esa es la belleza de las coordenadas homogéneas , que tienen gran aplicación en computación gráfica. Sin esto, no sería posible implementar operaciones afines como la traslación como una sola multiplicación de matrices, porque hace falta sumar una constante a las coordenadas. ¡La transformación afín se vuelve una transformación lineal en la dimensión superior!)

Algunos ejemplos de cómo se representan las transformaciones en forma matricial:

Traslación: desplazar la coordenada $x$ en $5$ , la $y$ en $7$ y la $z$ en $9$ .

$(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 7 & 9 & 1 \end{array})$

Escalado: escalar la coordenada $x$ por $10$ y las otras dos por $5$ .

$(\begin{array}{cccc} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \end{array})$

Rotación: rotar $\theta$ grados alrededor del eje $x$ siguiendo la regla de la mano derecha (sentido antihorario).

$(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \cos θ & - \sin θ & 0 \\ 0 & \sin θ & \cos θ & 0 \\ 0 & 0 & 0 & 1 \end{array})$

Ahora, una vez que cada transformación está descrita como una matriz, la secuencia de transformaciones se describe como un producto de esas matrices, y un “loop” de $k$ repeticiones se describe como la matriz elevada a la potencia $k$ (que se puede calcular con exponenciación binaria en $O(\log{k})$ ). Así, la matriz que representa todas las transformaciones se puede calcular primero en $O(m \log{k})$ , y después aplicarse a cada uno de los $n$ puntos en $O(n)$ para una complejidad total de $O(n + m \log{k})$ .

Número de caminos de longitud en un grafo { data-toc-label=‘Number of paths of length $k$ in a graph’ }

Problema: Dado un grafo dirigido no ponderado de $n$ vértices, encontrar la cantidad de caminos de longitud $k$ de cualquier vértice $u$ a cualquier otro vértice $v$ .

Solución: Este problema se trata con más detalle en un artículo separado. El algoritmo consiste en elevar la matriz de adyacencia $M$ del grafo (una matriz donde $m_{ij} = 1$ si hay una arista de $i$ a $j$ , o $0$ en caso contrario) a la $k$ -ésima potencia. Ahora $m_{ij}$ será la cantidad de caminos de longitud $k$ de $i$ a $j$ . La complejidad temporal de esta solución es $O(n^3 \log k)$ .

Nota: En ese mismo artículo se considera otra variante: cuando las aristas están ponderadas y hay que encontrar el camino de peso mínimo que contiene exactamente $k$ aristas. Como se muestra allí, este problema también se resuelve por exponenciación de la matriz de adyacencia. La matriz tendría el peso de la arista de $i$ a $j$ , o $\infty$ si no existe esa arista. En lugar de la operación usual de multiplicar dos matrices, hay que usar una modificada: en lugar de multiplicación se suman ambos valores, y en lugar de una sumatoria se toma un mínimo. Es decir: $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$ .

Variante de la exponenciación binaria: multiplicar dos números módulo { data-toc-label=‘Variation of binary exponentiation: multiplying two numbers modulo $m$ ’ }

Problema: Multiplicar dos números $a$ y $b$ módulo $m$ . $a$ y $b$ entran en los tipos de datos nativos, pero su producto es demasiado grande para entrar en un entero de 64 bits. La idea es calcular $a \cdot b \pmod m$ sin usar aritmética de bignums.

Solución: Simplemente aplicamos el algoritmo de construcción binaria descrito arriba, pero haciendo sumas en lugar de multiplicaciones. En otras palabras, “expandimos” la multiplicación de dos números a $O (\log m)$ operaciones de suma y de multiplicación por dos (que, en esencia, es una suma).

$a \cdot b =$

Nota: Se puede resolver esta tarea de otra forma usando operaciones de punto flotante. Primero se calcula la expresión $\frac{a \cdot b}{m}$ con números de punto flotante y se la castea a un entero sin signo $q$ . Se resta $q \cdot m$ de $a \cdot b$ usando aritmética de enteros sin signo y se toma módulo $m$ para encontrar la respuesta. Esta solución parece poco confiable, pero es muy rápida y muy fácil de implementar. Ver aquí para más información.