La operación módulo en teoría de números y cómo la implementan diferentes lenguajes

En informática, la operación módulo, dados dos números, D el dividendo y d el divisor, nos da el resto r de la división entera de D por d, siendo d≠0 y |r|<|d|. Aunque no parece gran cosa, aun menos teniendo en cuenta que hace décadas que las CPUs incorporan coprocesadores matemáticos capaces de hacer a gran velocidad operaciones aparentemente más relevantes como raíces o logaritmos, la realidad es que es una operación fundamental en informática. Desde la generación de tablas de hash y números aleatorios hasta la criptografía y la generación de checksums. Incluso ciertas operaciones aritméticas y lógicas, a nivel interno el ordenador las resuelve con aritmética modular, por ejemplo XOR es el resultado del módulo 2 (10 en binario) de la suma de dos bits.

Veamos como Python resuelve esta operación. Abrimos la consola de Python y mediante el operador % le pedimos el módulo con D=27 y d=13:

>>> 27%13
 1

Así es: 27 = 13 * 2 + 1

Lo mismo nos devuelve PHP:

echo 27%13;
1

Nada nuevo bajo el sol, matemáticas básicas. Probemos esto ahora:

>>> -27%13
12

Así es: -27 = 13 * (-3) + 12

Cambiando los signos de D y d:

>>> 27%-13
-12

¡¿Comorll?!?

El resultado esperado es 1:

27 = -13 * (-2) + 1

¿Por qué da -12? ¿Y PHP qué opina de todo esto?

echo 27%-13;
1

Buen chico. ¿Será que un lenguaje tan usado y prestigioso como Python no sabe dividir? ¿Por qué entonces lo escogen en tantas facultades de todo el mundo para la enseñanza? La NASA también lo usa, ¿han escogido un lenguaje que no sabe ni calcular el resto de una división entera?

Siguiendo con PHP:

echo -27%13;
-1

Habíamos visto antes que el resultado era 12 ¿PHP anda también perdido? La definición de la Wikipedia tampoco ayuda a esclarecer que está pasando. En mi opinión, esa definición es inexacta pues dice que la operación módulo calcula el resto de la división euclídea y en la división euclídea se impone la condición r ≥ 0 Cuando no se impone esa condición, y no lo hice en la definición de la operación módulo que di al iniciar esta entrada, las divisiones tendrán dos cocientes y dos residuos posibles: por defecto y por exceso. Mientras que con r ≥ 0 sólo habrá un resultado posible. Si hay un cociente q habrá otro cociente q’ cuyo valor será q + 1 y cada cociente tendrá su respectivo residuo r y r’ Con D=-27 y d=13 tendremos q=-3 y r=12 por un lado y por otro q=-2 y r=-1

-27 = 13 * (-3) + 12

-27 = 13 * (-2) + (-1)

Por lo tanto ambos lenguajes están calculando correctamente. En teoría de números siempre se escoge r ≥ 0 y algunos lenguajes, como Pascal, Scheme o Stata así lo hacen también, para estos lenguajes sí aplica la definición de la Wikipedia, pero la mayoría y los más usados van a escoger la división por exceso o por defecto. Algunos, como PHP, C o C++ escogerán siempre para el resto el signo del dividendo D mientras que otros como Python o Mathematica el del divisor d. Aparentemente para conseguir esta igualdad de signo, usarán la división por exceso o por defecto según sea necesario, aunque lo que realmente hacen es una operación más rápida. Los que usan el mismo signo que el dividendo van realmente rápido, truncan la división:

r = D – d * truncar(D / d)

La función truncar simplemente extermina todos los decimales, o dicho más fino: se redondea al número entero inmediato más cercano a 0. Esto es lo que hace PHP o C:

-1 = -27 – [13*truncar(-27 / 13)] = -27 – [13*truncar(-2.07…)] = -27 – [13*(-2)] = -27 – (-26)

Por otro lado, los que usan el signo del divisor d, usan la función floor (suelo). Esta función proporciona el número entero más pequeño inmediato o igual al número que se le pasa. De manera que por ejemplo Π quedaría en 3 y -Π en -4. Está función se expresa mediante ⌊⌋: floor(x) = ⌊x⌋

r = D – d * ⌊D / d⌋

Esto es lo que Python hace:

12 = -27 – 13[⌊-27 / 13⌋] = -27 – 13[⌊-2.07…⌋] = -27 -13[-3] = -27 + 39

Con la primera extrañeza que nos encontramos, cuando pusimos un divisor negativo, ahora sabemos qué hace Python:

-12 = 27 – (-13)*[⌊27 / -13⌋] = 27 – (-13)⌊-2.07…⌋ = 27 – (-13)*(-3) = 27 – 39

Lenguajes respetuosos con la teoría, como Pascal, hacen esto:

Si d > 0 => q = ⌊D / d⌋

Si d < 0 => q = ⌈D / d⌉

Es decir, si el divisor es negativo usan la función ceiling (techo) Dicha función da el número entero más grande inmediato o igual al número que se le pasa. De manera que Π quedaría en 4 y -Π en -3. Está función se expresa mediante ⌈⌉: ceiling(x) =⌈x⌉

Hay que tener en cuenta que no es esto lo que hacen los lenguajes que cogen el signo del divisor, es decir, no es lo mismo ⌊x⌋ que truncar(), no en el caso de números negativos. Volviendo al ejemplo D = 27 y d = -13 que en Python dio r = -12 mientras que PHP r = 1:

-12 ≠ 27 – (-13*⌈27 / -13⌉) = 27 – (-13*(-2)) = 27 – 26 = 1

Es lo que nos devolvió PHP, porque para números negativos truncar(x) equivale a ⌈x⌉ Para los positivos, en cambio, truncar(x) equivale a ⌊x⌋, por eso para D y d positivos todo lenguaje da el mismo r. Las diferencias surgen con los negativos. Veamos el caso en que ambos son negativos, D = -27 y d = -13. PHP usa truncar(), que en este caso sí equivale a ⌈⌉ :

-27 – (-13* truncar(-27 / -13) = -27 – (-13*truncar(2.07)) = -27 – (-13*2) = -27 + 26 = -1

>>> -27%-13
-1
echo -27%-13;
-1

Mientras que ⌊⌋, que ningún lenguaje la usa, daría:

-27 – (-13*⌊-27 / -13⌋) = -27 – (-13*(⌊2.07⌋) = -27 – (-13)*3 = -27 + 39 = 12

Como q = (D – r) / d Acaba resultando una ecuación sin solución entera:

(-27 – 12) / -13

Por lo tanto r ≠ 12

En la definición de división entera que di al principio introduje una “trampa” para que los resultados de PHP, Python o C fueran correctos: añadí la condición |r|<|d| En teoría de números, la división entera se define sólo para el conjunto de los naturales y la única condición es d ≠ 0 En cambio, para el conjunto de los números enteros (que incluye los naturales más los negativos), se usa la división euclídea, la cual añade la condición r ≥ 0 con el objetivo de obtener unos q y r únicos.

En mi opinión, la razón principal por la que algunos lenguajes usan la división entera también para números negativos es obtener un conjunto de r más amplio. Sin la condición r ≥ 0 se obtienen también r negativos. Con ello, por ejemplo, se consigue reducir el número de colisiones en una tabla de hash. Secundariamente, porque es más rápido el cálculo: truncar es más rápido que redondear. Sacrifican purismo matemático por fines prácticos. Además, el programador puede seguir obteniendo el resto de la división euclídea por otras vías. Puede programar su propia función con ceil() y floor(), o con floor() y truncate() si viene de microsegundos. También es más que probable que el lenguaje tenga una función para obtener dicho resto. Por ejemplo C tiene la función fmod en la librería math.h

3 pensamientos en “La operación módulo en teoría de números y cómo la implementan diferentes lenguajes

  1. Pingback: Cálculo del mcd y la identidad de Bezout | Víctor Iglesias

  2. Pingback: Programa para resolver ecuaciones diofánticas | Víctor Iglesias

  3. Pingback: El número e elevado a un número complejo imaginario puro

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.