sábado, 23 de abril de 2011

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;
 }




0 comentarios:

Publicar un comentario en la entrada