Algoritmo de Garner

Una consecuencia del Teorema Chino del Resto es que podemos representar números grandes usando un arreglo de enteros pequeños. Por ejemplo, sea $p$ el producto de los primeros $1000$ primos. $p$ tiene alrededor de $3000$ dígitos.

Cualquier número $a$ menor que $p$ se puede representar como un arreglo $a_1, \ldots, a_k$ , donde $a_i \equiv a \pmod{p_i}$ . Pero para hacer esto, obviamente, necesitamos saber cómo recuperar el número $a$ a partir de su representación. Una forma se discute en el artículo sobre el Teorema Chino del Resto.

En este artículo discutimos una alternativa, el algoritmo de Garner, que también se puede usar para este propósito.

Representación en base mixta

Podemos representar el número $a$ en la representación de base mixta (mixed radix):

$a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \cdots p_{k-1} \text{ with }x_i \in [0, p_i)$

Una representación en base mixta es un sistema de numeración posicional, que generaliza los sistemas numéricos típicos, como el sistema binario o el sistema decimal. Por ejemplo, el sistema decimal es un sistema de numeración posicional con radix (o base) 10. Todo número se representa como una cadena de dígitos $d_1 d_2 d_3 \dots d_n$ entre $0$ y $9$ . Por ejemplo, la cadena $415$ representa el número $4 \cdot 10^2 + 1 \cdot 10^1 + 5 \cdot 10^0$ . En general, la cadena de dígitos $d_1 d_2 d_3 \dots d_n$ representa el número $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$ en el sistema de numeración posicional con radix $b$ .

En un sistema de base mixta ya no tenemos un único radix. La base varía de una posición a otra.

Algoritmo de Garner

El algoritmo de Garner calcula los dígitos $x_1, \ldots, x_k$ . Nótese que los dígitos son relativamente pequeños. El dígito $x_i$ es un entero entre $0$ y $p_i - 1$ .

Sea $r_{ij}$ el inverso de $p_i$ módulo $p_j$

$r_{ij} = (p_i)^{-1} \pmod{p_j}$

que se puede encontrar usando el algoritmo descrito en Inverso modular.

Sustituyendo $a$ de la representación en base mixta en la primera ecuación de congruencia obtenemos

$a_1 \equiv x_1 \pmod{p_1}.$

Sustituyendo en la segunda ecuación se obtiene

$a_2 \equiv x_1 + x_2 p_1 \pmod{p_2},$

que se puede reescribir restando $x_1$ y dividiendo por $p_1$ para llegar a

$\begin{array}{rclr} a_{2} - x_{1} & \equiv & x_{2} p_{1} & (m o d p_{2}) \\ (a_{2} - x_{1}) r_{12} & \equiv & x_{2} & (m o d p_{2}) \\ x_{2} & \equiv & (a_{2} - x_{1}) r_{12} & (m o d p_{2}) \end{array}$

De forma similar obtenemos que

$x_3 \equiv ((a_3 - x_1) r_{13} - x_2) r_{23} \pmod{p_3}.$

Ahora se ve claramente un patrón emergente, que se puede expresar con el siguiente código:


for (int i = 0; i < k; ++i) {
    x[i] = a[i];
    for (int j = 0; j < i; ++j) {
        x[i] = r[j][i] * (x[i] - x[j]);
 
        x[i] = x[i] % p[i];
        if (x[i] < 0)
            x[i] += p[i];
    }
}

Así aprendimos a calcular los dígitos $x_i$ en tiempo $O(k^2)$ . El número $a$ se puede calcular ahora usando la fórmula mencionada antes

$a = x_1 + x_2 \cdot p_1 + x_3 \cdot p_1 \cdot p_2 + \ldots + x_k \cdot p_1 \cdots p_{k-1}$

Vale la pena señalar que, en la práctica, casi con seguridad necesitamos calcular la respuesta $a$ usando aritmética de precisión arbitraria, pero los dígitos $x_i$ (porque son pequeños) suelen poder calcularse con tipos nativos, y por eso el algoritmo de Garner es muy eficiente.

Implementación del algoritmo de Garner

Es conveniente implementar este algoritmo en Java, porque tiene soporte nativo para números grandes a través de la clase BigInteger.

Aquí mostramos una implementación que puede almacenar números grandes en forma de un conjunto de ecuaciones de congruencia. Soporta suma, resta y multiplicación. Y con el algoritmo de Garner podemos convertir el conjunto de ecuaciones en el entero único. En este código tomamos 100 números primos mayores que $10^9$ , lo que permite representar números tan grandes como $10^{900}$ .


final int SZ = 100;
int pr[] = new int[SZ];
int r[][] = new int[SZ][SZ];
 
void init() {
    for (int x = 1000 * 1000 * 1000, i = 0; i < SZ; ++x)
        if (BigInteger.valueOf(x).isProbablePrime(100))
            pr[i++] = x;
 
    for (int i = 0; i < SZ; ++i)
        for (int j = i + 1; j < SZ; ++j)
            r[i][j] =
                BigInteger.valueOf(pr[i]).modInverse(BigInteger.valueOf(pr[j])).intValue();
}
 
class Number {
    int a[] = new int[SZ];
 
    public Number() {
    }
 
    public Number(int n) {
        for (int i = 0; i < SZ; ++i)
            a[i] = n % pr[i];
    }
 
    public Number(BigInteger n) {
        for (int i = 0; i < SZ; ++i)
            a[i] = n.mod(BigInteger.valueOf(pr[i])).intValue();
    }
 
    public Number add(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (a[i] + n.a[i]) % pr[i];
        return result;
    }
 
    public Number subtract(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (a[i] - n.a[i] + pr[i]) % pr[i];
        return result;
    }
 
    public Number multiply(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (int)((a[i] * 1l * n.a[i]) % pr[i]);
        return result;
    }
 
    public BigInteger bigIntegerValue(boolean can_be_negative) {
        BigInteger result = BigInteger.ZERO, mult = BigInteger.ONE;
        int x[] = new int[SZ];
        for (int i = 0; i < SZ; ++i) {
            x[i] = a[i];
            for (int j = 0; j < i; ++j) {
                long cur = (x[i] - x[j]) * 1l * r[j][i];
                x[i] = (int)((cur % pr[i] + pr[i]) % pr[i]);
            }
            result = result.add(mult.multiply(BigInteger.valueOf(x[i])));
            mult = mult.multiply(BigInteger.valueOf(pr[i]));
        }
 
        if (can_be_negative)
            if (result.compareTo(mult.shiftRight(1)) >= 0)
                result = result.subtract(mult);
 
        return result;
    }
}