Algoritmo Big Mod

Pongamos que tenemos que calcular el módulo o resto de la división de un número de muchas cifras entre otro más pequeño, lo suficiente para que pueda almacenarse en un int, o en un long int.

No es algo que no nos vayamos a encontrar nunca. De hecho, la razón de esta entrada es que he necesitado hacer estas operaciones, y pronto veremos un ejemplo en una entrada posterior.

En principio no parece fácil, pero las matemáticas vienen en nuestra ayuda. Concretamente la teoría de números.

El algoritmo que vamos a ver, como dice el título se llama Big Mod.

Este algoritmo se basa en estas dos propiedades:

(a*b*c) mod m =((a mod m)*(b mod m)*(c mod m)) mod m (1)
(a+b+c) mod m =((a mod m)+(b mod m)+(c mod m)) mod m (2)

Primero veamos qué significa exactamente calcular el módulo de una división.

dividendo  = cociente * divisor + resto

Hay que tener en cuenta que, a la hora de calcular el resto, nos podemos despreocupar del valor del cociente. Esto nos puede ayudar, porque el resto es el mismo si restamos del dividendo el divisor un número entero de veces:

dividendo - n * divisor = (cociente-n) * divisor + resto

Por otra parte, si descomponemos el dividendo en dos factores, a y b:

a*b = cociente * divisor + resto

(a-n*divisor)*(b-m*divisor) = (cociente-n-m) * divisor + resto

Es decir, el resto es el mismo si restamos de cualquiera de los factores un múltiplo del divisor.

Lo mismo sirve para sumas, si descomponemos el dividendo en dos sumandos c y d:

c+d = cociente * divisor + resto

(c-n*divisor)+(d-m*divisor) = (cociente-n-m) * divisor + resto

Esto es, el resto es el mismo si restamos de cualquiera de los sumandos un múltiplo del divisor.

¿Cómo nos ayuda esto a resolver nuestro problema?

Veamos un ejemplo:

5657866541284565 % 67 =

(565*10¹³+7866541284565) % 67

Ahora, podemos restar del primer número, el 565 el valor 67, tantas veces como queramos. Lo haremos el máximo, es decir, nos quedaremos con el resto de 565/67, o lo que es lo mismo, 565 % 67 = 29.

(29*10¹³+7866541284565) % 67

O:

297866541284565 % 67

Como se puede ver, hemos disminuido en una unidad los dígitos del número grande.

Podemos aplicar esta técnica recursivamente, o mejor, iterativamente.

Algoritmo

1. Partimos de n igual a cero.
2. Tomamos un dígito de la izquierda del número grande y lo añadimos a la derecha de n.
3. Calculamos el módulo n % d, y lo guardamos en n.
4. Repetimos desde 2, hasta terminar los dígitos del número grande.
5. n contiene el valor del módulo.

5657866541284565 % 67

5 % 67 = 5

56 % 67 = 56

565 % 67 = 29

297 % 67 = 29

298 % 67 = 30

306 % 67 = 38

etc.

Código C++

Una implementación sencilla es esta:

int moduloNG(const char *numero, int d) {
    int i = 0, n = 0;

    while(numero[i]) {
        n = n * 10 + numero[i] - '0';
        n = n % d;
        i++;
    }
    return n;
}

Otra, más compacta:

int moduloNG(const char *numero, int d) {
    int i = 0, n = 0;

    while(numero[i]) n = (n * 10 + numero[i++] - '0') % d;
    return n;
}