Divisiones y módulos enteros

Supongamos que queremos saber si un número es impar. ¿Bastaría este código?

bool impar(int n)
{
 return (n%2) == 1;
}

Veamos. Introducimos el valor 5, hacemos la división por 2 y obtenemos el resto 1. Efectivamente, es impar. Ahora introduzcamos el valor -3, hacemos la división por 2 y obtenemos ¿qué resto? En mi implementación obtengo -1. Eso es un problema, pero ¿por qué sale -1? ¿No debería salir 1?

El operador de módulo % está muy relacionado con la división entera. La división entera se define de la siguiente manera. Sean cuatro números enteros [$n, d, c$] y [$r$] que llamaremos dividendo, divisor, cociente y resto. Esos cuatro números cumplen la siguiente ecuación.

[$$ n = dc + r $$]

Si, además, imponemos la siguiente inecuación, el cociente y el resto son únicos para cada par de dividendo y divisor.

[$$ 0\le r \lt \left| d \right| $$]

Esto es, básicamente, la llamada división euclídea. Matemáticamente este procedimiento de división es muy interesante y tiene muchas propiedades, pero carece de otras. En concreto, con esta división entera multiplicar divisor y dividendo por menos uno altera el resultado.

[$$ \frac{a}{b} \ne \frac{-a}{-b} $$]

Se puede probar con, por ejemplo, [$ \frac{7}{3} $] el cociente será [$2$] y el resto [$1$] mientras que [$ \frac{-7}{-3} $] tiene cociente [$3$] y resto [$2$]. No puedo obtener cociente [$2$] porque el resto tiene que ser positivo.

Entonces, usemos una división más intuitiva. Por ejemplo, hacemos la división en los reales y luego redondeamos. Ahora bien, hay varios tipos de redondeo. Los más usuales son el redondeo por truncamiento, por defecto, por exceso y al entero más cercano (con varias estrategias de desempate).

Según usemos un tipo de división u otra, obtendremos el resto (es decir, el resultado del operador %) de una forma u otra, pero todas mediante la ecuación anterior para mantener consistencia. Despejamos de ella el resto y esa es nuestra definición del operador %.

[$$ n\%d = r = n - dc = n - d \left[ \frac{n}{d} \right] $$]

La división entre corchetes representa el cociente que cambiará según elijamos uno u otro redondeo. El resumen está en esta tabla.

	Redondeo por truncamiento	Redondeo por defecto	Redondeo por exceso	Redondeo al más cercano	División euclídea
[$$\frac{3}{5}$$]	c=0 r=3	c=0 r=3	c=1 r=-2	c=1 r=-2	c=0 r=3
[$$\frac{-3}{5}$$]	c=0 r=-3	c=-1 r=2	c=0 r=-3	c=-1 r=2	c=-1 r=2
[$$\frac{3}{-5}$$]	c=0 r=3	c=-1 r=-2	c=0 r=3	c=-1 r=-2	c=0 r=3
[$$\frac{-3}{-5}$$]	c=0 r=-3	c=0 r=-3	c=1 r=2	c=1 r=2	c=1 r=2

Hay tres hechos importantes en esta tabla:

1. En el redondeo por truncamiento el signo del resto coincide con el signo del dividendo.
2. En el redondeo por defecto el signo del resto coincide con el signo del divisor (y en el redondeo por exceso con su opuesto).
3. En el redondeo al entero más cercano el resto es el más cercano a cero posible.

Nota: La división que utilizamos cuando usamos el AND binario (&) para calcular rápidamente un módulo [$ a\% 2^n = a \& (2^n -1) $] es o bien la por defecto o la euclídea (tanto el divisor como el resto son positivos en este caso).

Ahora sólo queda ver qué lenguaje de programación usa qué tipo de división y módulo. La siguiente tabla extraída de la Wikipedia lo lista.

Lenguaje	Operador	El resultado tiene el mismo signo que
ActionScript	%	Dividendo
Ada	mod	Divisor
	rem	Dividendo
ASP	Mod	No definido
ALGOL-68	%×	Euclídea
AMPL	mod	Dividendo
AppleScript	mod	Dividendo
BASIC	Mod	No definido
bc	%	Dividendo
bash	%	Dividendo
C (ISO 1990)	%	Depende de implementación
C (ISO 1999)	%	Dividendo
C++	%	Depende de implementación
C#	%	Dividendo
CLARION	%	Dividendo
Clojure	mod	Divisor
ColdFusion	%	Dividendo
Common Lisp	mod	Divisor
	rem	Dividendo
D	%	Dividendo
Eiffel	\\	Dividendo
Erlang	rem	Dividendo
Euphoria	mod	Divisor
	remainder	Dividendo
FileMaker	Mod	Divisor
Fortran	mod	Dividendo
	modulo	Divisor
GML (Game Maker)	mod	Dividendo
Go	%	Dividendo
Haskell	mod	Divisor
	rem	Dividendo
J	|~	Divisor
Java	%	Dividendo
JavaScript	%	Dividendo
Just Basic	MOD	Dividendo
Lua 5	%	Divisor
Lua 4	mod(x,y)	Divisor
Liberty Basic	MOD	Dividendo
MathCad	mod(x,y)	Divisor
Maple (software)	e mod m	Divisor
Mathematica	Mod	Divisor
Microsoft Excel	=MOD()	Divisor
MATLAB	mod	Divisor
	rem	Dividendo
Oberon	MOD	Divisor
Objective Caml	mod	Dividendo
Occam	\	Dividendo
Pascal (Delphi)	mod	Dividendo
Pascal (ISO-7185 and ISO-10206)	mod	Euclídea
Perl	%	Divisor
PHP	%	Dividendo
PL/I	mod	Divisor (ANSI PL/I)
PowerBuilder	mod(x,y)	?
PowerShell	%	Dividendo
Prolog (ISO 1995)	mod	Divisor
	rem	Dividendo
Python	%	Divisor
RealBasic	MOD	Dividendo
R	%%	Divisor
RPG	%REM	Dividendo
Ruby	%, modulus()	Divisor
	remainder()	Dividendo
Scheme	modulo	Divisor
	remainder	Dividendo
Scheme R6RS	mod	Euclídea
	mod0	Más cercano a cero
SenseTalk	modulo	Divisor
	rem	Dividendo
Smalltalk	\\	Divisor
SQL (SQL:1999)	mod(x,y)	Dividendo
Standard ML	mod	Divisor
	Int.rem	Dividendo
Stata	mod(x,y)	Euclídea
Tcl	%	Divisor
Torque Game Engine	%	Dividendo
Turing (programming language)	mod	Divisor
Verilog (2001)	%	Dividendo
VHDL	mod	Divisor
	rem	Dividendo
Visual Basic	Mod	Dividendo
x86 Assembly	IDIV	Dividendo
ADEP_AUTO language	MODULO(x,y)	Divisor

También existe el mismo problema relacionado con la operación equivalente en los reales (flotantes). Esta es la tabla en este caso.

Lenguaje	Operador	El resultado tiene el mismo signo que
C (ISO 1990)	fmod	?
C (ISO 1999)	fmod	Dividendo
	remainder	Más cercano a cero
C++	std::fmod	?
C#	%	Dividendo
D	%	?
Common Lisp	mod	Divisor
	rem	Dividendo
Go	math.Fmod	Dividendo
Haskell (GHC)	Data.Fixed.mod'	Divisor
Java	%	Dividendo
JavaScript	%	Dividendo
Objective Caml	mod_float	Dividendo
Perl	POSIX::fmod	Dividendo
PHP	fmod	Dividendo
Python	%	Divisor
	math.fmod	Dividendo
Ruby	%, modulus()	Divisor
	remainder()	Dividendo
Scheme R6RS	flmod	Euclídea
	flmod0	Más cercano a cero
Standard ML	Real.rem	Dividendo

Bueno. Entonces. Al final. ¿Cómo sé si un número es impar o no? Lo mejor es aprovechar que el resto cero es igual en todas las implementaciones y hacer algo así.

bool impar(int n)
{
 return (n%2) != 0;
 }