Resto negativo vs módulo

¿Cuál es el residuo de dividir $7$ por $-3$? De hecho, puede ser $1$ o $-2$, dependiendo de la convención elegida y/o el lenguaje de programación en uso.

¿Qué? ¿Residuos negativos? Veamos esto en detalle.

División en matemáticas

En matemáticas, la división fundamentalmente trata de dividir una cantidad en partes iguales.

Cuando dividimos un número $a$ por otro número $b$, estamos preguntando: “¿Cuántos $b$ podemos encajar en $a$?”

División euclidiana

La división euclidiana, también conocida como división entera, es específicamente un tipo de división aplicada a números enteros.

Veamos la fórmula: $$ a=b*q+r $$

Aquí, tenemos:

• dividendo ($a$): el número que está siendo dividido
  • p.ej., en $7 / 3$, el dividendo es $7$
• divisor ($b$): el número por el que usted divide
  • p.ej., en $7 / 3$, el divisor es $3$

La división euclidiana nos da dos valores importantes al dividir enteros:

• cociente entero ($q$): la división da un resultado de número entero (redondeando hacia abajo)
  • p.ej., $7 / 3$ tiene un cociente de $2$
• residuo entero ($r$): la parte sobrante después de la división es un entero
  • p.ej., $7 - (3 × 2) = 1$

Además, esto debe ser verdad: $$ b \neq 0 \\[1em] 0 \leq r < |b| \\[1em] 0 \leq residuo < |divisor| \quad \text{← igual que arriba} $$

Observe cuidadosamente:

• $b$ puede ser negativo, pero no puede ser $0$
• $r$ es un número positivo menor que el valor absoluto $|b|$ (divisor) y puede ser $0$.

Ejemplos de división euclidiana para matemáticas puras

Veamos cómo las matemáticas puras manejarán todos los casos:

• Dividendo positivo, divisor positivo: $$ 7 \bmod 3 = 1 \\ 7 = 3 * 2 + 1 $$

• Dividendo positivo, divisor negativo: $$ 7 \bmod (-3) = 1 \\ 7 = (-3) * (-2) + 1 $$

• Dividendo negativo, divisor positivo. Preste atención a que encontramos el cociente ($-3$) para que el resultado ($-9$) sea menor que el dividendo ($-7$): $$ -7 \bmod 3 = 2 \\ -7 = 3 * (-3) + 2 $$

• Dividendo negativo, divisor negativo. Preste atención a que encontramos el cociente ($3$) para que el resultado ($-9$) sea menor que el dividendo ($-7$): $$ (-7) \bmod (-3) = 2 \\ -7 = (-3) * 3 + 2 $$

Como puede ver, redondeamos hacia abajo el resultado de $cociente * divisor$ incluso para los números negativos, por lo tanto el residuo es positivo en matemáticas (en la mayoría de las convenciones).

Módulo vs Congruencia módulo

El residuo puede ser calculado usando la operación de módulo: $$ r = a \bmod b $$

Es importante no confundir la operación de módulo y la relación de congruencia módulo.

Congruencia módulo se denota como: $$ a \equiv b \pmod{m} $$

y esencialmente significa que: $$ a \bmod m = b \bmod m $$

En otras palabras: $a$ y $b$ dan el mismo residuo cuando se dividen por $m$.

Residuos en programación

Como vimos anteriormente, en matemáticas, el residuo es un número positivo (de nuevo, en la mayoría de las convenciones).

Sin embargo, la operación de calcular el residuo en lenguajes de programación puede devolver un resultado negativo (para un dividendo o divisor negativo).

Hay dos opciones aquí:

• El signo del residuo coincide con el signo del dividendo
  • El cociente incompleto se redondea a $0$.
• El signo del residuo coincide con el signo del divisor
  • El cociente incompleto se redondea a $−\infty$.

Analicemos cada caso a continuación.

Signo del residuo = signo del dividendo

El cociente incompleto se redondea en dirección a $0$.

Veamos los casos:

• Dividendo positivo, divisor positivo: $$ 7 \bmod 3 = 1 \\[1em] 7 / 3 = 2.333(3) \approx 2 \quad \text{redondeando a $0$} \\[1em] 7 = 3 * 2 + 1 $$

• Dividendo positivo, divisor negativo: $$ 7 \bmod (-3) = 1 \\[1em] 7 / (-3) = -2.333(3) \approx -2 \quad \text{redondeando a $0$} \\[1em] 7 = (-3) * (-2) + 1 $$

• Dividendo negativo, divisor positivo. Usted ve que el cociente es $-2$ aquí, no $-3$, como en matemáticas regulares: $$ (-7) \bmod 3 = -1 \\[1em] (-7) / 3 = -2.333(3) \approx -2 \quad \text{redondeando a $0$} \\[1em] -7 = 3 * (-2) + (-1) $$

• Dividendo negativo, divisor negativo. Usted ve que el cociente es $2$ aquí, no $3$, como en matemáticas regulares: $$ (-7) \bmod (-3) = -1 \\[1em] (-7) / (-3) = 2.333(3) \approx 2 \quad \text{redondeando a $0$} \\[1em] -7 = (-3) * 2 + (-1) $$

Signo del residuo = signo del divisor

El cociente incompleto se redondea en dirección a $-\infty$.

Veamos los casos:

• Dividendo positivo, divisor positivo: $$ 7 \bmod 3 = 1 \\[1em] 7 / 3 = 2.333(3) \approx 2 \quad \text{redondeando a $−\infty$} \\[1em] 7 = 3 * 2 + 1 $$

• Dividendo positivo, divisor negativo. Usted ve que el cociente es $-3$ aquí, no $-2$, como en matemáticas regulares: $$ 7 \bmod -3 = -2 \\[1em] 7 / (-3) = -2.333(3) \approx -3 \quad \text{redondeando a $−\infty$} \\[1em] 7 = (-3) * (-3) + (-2) $$

• Dividendo negativo, divisor positivo: $$ -7 \bmod 3 = 2 \\[1em] -7 / 3 = -2.333(3) \approx -3 \quad \text{redondeando a $−\infty$} \\[1em] -7 = 3 * (-3) + 2 $$

• Dividendo negativo, divisor negativo. Usted ve que el cociente es $2$ aquí, no $3$, como en matemáticas regulares: $$ (-7) \bmod (-3) = -1 \\[1em] (-7 / (-3) = 2.333(3) \approx 2 \quad \text{redondeando a $−\infty$} \\[1em] -7 = (-3) * 2 + (-1) $$

‼️ Como puede ver, ambos casos en ciencias de la computación (coincide con el signo del dividendo y coincide con el signo del divisor) son diferentes de los principios de matemáticas puras.

Detalles de implementación

Es importante tener en cuenta que el comportamiento de la operación de residuo varía dependiendo del lenguaje de programación.

Algunos lenguajes redondean hacia cero, mientras que otros redondean hacia el infinito negativo.

Hay dos tipos de división:

• División truncada: $3.75$ equivale a $3$, y $-3.75$ equivale a $-3$.
• División de piso: $3.75$ equivale a $3$, pero $-3.75$ equivale a $-4$ (redondea hacia abajo, Math.floor())

Implementación en Java

En Java, la operación de módulo (%) sigue la regla donde el residuo toma el signo del dividendo (el primer operando).

La operación de módulo de Java se define por la fórmula:

a % b = a - (a / b) * b

donde / es división entera (truncada) que redondea hacia cero.

Implementación en Python

En Python, el operador de módulo (%) sigue la regla donde el residuo toma el signo del divisor (el segundo operando).

La operación de módulo de Python se define por la fórmula:

a % b = a - (a // b) * b

donde // es división de piso que redondea hacia el infinito negativo.

Aplicaciones prácticas

Uno puede preguntar – espere, ¿por qué necesitamos múltiples formas de calcular residuos?

Bueno, cada una de las formas tiene sus aplicaciones en la vida real.

Signo del residuo = signo del dividendo

Hay un número de n centavos, positivo o negativo. Uno necesita convertirlo a dólares y centavos. Será:

dólares = n div 100
centavos = n mod 100

El signo del residuo coincide con el signo del dividendo.

Signo del residuo = signo del divisor

Hay una cuadrícula infinita de celdas, cada celda es de 16×16 píxeles. ¿En qué celda cae el punto (x, y), y cuáles son sus coordenadas relativas a la esquina superior izquierda de la celda? La respuesta:

x div 16, y div 16
// y
(x mod 16, y mod 16)

El signo del residuo coincide con el signo del divisor.

Comportamiento del módulo entre lenguajes

Dado que cada lenguaje tiene ambos tipos de división, podemos programar cada comportamiento de módulo en cada lenguaje.

Python:

python_mod = a - (a // b) * b  # división de piso
java_mod = a - int(a / b) * b  # división truncada

Java:

// división de piso
int pythonMod = (int) (a - Math.floor((double) a / (double) b) * b);

// división truncada
int javaMod = a - (a / b) * b;

Implementación del resto positivo

Pero, ¿qué pasa si necesitamos que el resto siempre sea positivo en la programación?

No podemos simplemente tomar el valor absoluto, ya que recordarás que un resto negativo significa que estamos “al otro lado” del objetivo de destino.

Existe una técnica común para asegurar que el resultado de la operación módulo siempre esté en el rango no negativo [0, a-1], independientemente del signo de el resto original o de cómo se implemente la operación módulo en un lenguaje o contexto particular: $$ (a \bmod b + b) \bmod b $$

Vamos a desglosarlo:

1. a mod b: esto calcula el resto inicial. Dependiendo del signo de el resto, esto podría ser negativo (por ejemplo, $-1 \bmod 5$ podría devolver $-1$ en algunos contextos)
2. + b: esto desplaza los resultados negativos al rango positivo. Por ejemplo, $-1 + 5 = 4$
3. mod b: incluso si el resto era positiva originalmente, esto asegura que el resultado final siga estando dentro de [0, a-1].

Veamos más de cerca:

1. a mod b:

• En Java -1 mod 5 = -1.
• En Python -1 mod 5 directamente devuelve $4$.

2. + b:

• Si el primer resultado fue $-1$: $-1 + 5 = 4$ (ahora un valor positivo).
• Si el primer resultado ya era $4$: $4 + 5 = 9$ (temporalmente excede el rango del módulo).

3. mod b:

• Si tenías $4$ del primer paso: 4 mod 5 = 4 (sin cambios).
• Si tenías $9$ del primer paso: 9 mod 5 = 4 (lo devuelve al rango [0, 4]).