En informática , la operación de módulo devuelve el resto o resto con signo de una división , después de dividir un número por otro (llamado módulo de la operación).
Dados dos números positivos a y n , un módulo n (a menudo abreviado como mod n ) es el resto de la división euclidiana de a por n , donde a es el dividendo y n es el divisor . [1]
Por ejemplo, la expresión "5 mod 2" se evalúa como 1, porque 5 dividido por 2 tiene un cociente de 2 y un resto de 1, mientras que "9 mod 3" se evalúa como 0, porque 9 dividido por 3 tiene un cociente de 3 y un resto de 0.
Aunque normalmente se realiza con a y n como números enteros , muchos sistemas informáticos ahora permiten otros tipos de operandos numéricos. El rango de valores para una operación de módulo entero de n es de 0 a n − 1 ( un mod 1 es siempre 0; un mod 0 no está definido, ya que es una división por cero ).
Cuando exactamente uno de a o n es negativo, la definición básica se rompe y los lenguajes de programación difieren en la forma en que se definen estos valores.
En matemáticas , el resultado de la operación de módulo es una clase de equivalencia , y cualquier miembro de la clase puede ser elegido como representante ; sin embargo, el representante habitual es el residuo menos positivo , el entero no negativo más pequeño que pertenece a esa clase (es decir, el resto de la división euclidiana ). [2] Sin embargo, son posibles otras convenciones. Las computadoras y calculadoras tienen varias formas de almacenar y representar números; por lo tanto, su definición de la operación del módulo depende del lenguaje de programación o del hardware subyacente .
En casi todos los sistemas informáticos, el cociente q y el resto r de a dividido por n satisfacen las siguientes condiciones:
Esto todavía deja un signo de ambigüedad si el resto es distinto de cero: se producen dos opciones posibles para el resto, una negativa y otra positiva; esa elección determina cuál de los dos cocientes consecutivos debe usarse para satisfacer la ecuación (1). En teoría de números siempre se elige el resto positivo, pero en informática los lenguajes de programación eligen dependiendo del lenguaje y de los signos de a o n . [a] Pascal estándar y ALGOL 68 , por ejemplo, dan un resto positivo (o 0) incluso para divisores negativos, y algunos lenguajes de programación, como C90, lo dejan a la implementación cuando cualquiera de n o a es negativo (consulte la tabla en § En lenguajes de programación para más detalles). un módulo 0 no está definido en la mayoría de los sistemas, aunque algunos lo definen como .
Muchas implementaciones utilizan división truncada , para la cual el cociente se define por
donde es la función de parte integral ( redondeo hacia cero ), es decir, el truncamiento a cero de dígitos significativos. Así, según la ecuación ( 1 ), el resto tiene el mismo signo que el dividendo a, por lo que puede tomar 2| norte | − 1 valores:
Donald Knuth [3] promueve la división piso , para la cual el cociente se define por
donde ⌊⌋ es la función suelo ( redondeando hacia abajo ). Así, según la ecuación ( 1 ), el resto tiene el mismo signo que el divisor n :
Raymond T. Boute [4] promueve la división euclidiana , para la cual el cociente se define por
donde sgn es la función de signo , ⌊⌋ es la función de piso ( redondeando hacia abajo ) y ⌈⌉ es la función de techo ( redondeando hacia arriba ). Así, según la ecuación ( 1 ), el resto no es negativo :
Common Lisp e IEEE 754 utilizan división redondeada , para la cual el cociente se define por
donde ronda es la función redonda ( redondear la mitad a par ). Por lo tanto, según la ecuación ( 1 ), el resto cae entre y , y su signo depende de en qué lado de cero cae para estar dentro de estos límites:
Common Lisp también utiliza la división de techo , para la cual el cociente se define por
donde ⌈⌉ es la función techo ( redondeando hacia arriba ). Así, según la ecuación ( 1 ), el resto tiene el signo opuesto al del divisor :
Si tanto el dividendo como el divisor son positivos, entonces las definiciones truncada, mínima y euclidiana concuerdan. Si el dividendo es positivo y el divisor es negativo, entonces las definiciones truncada y euclidiana concuerdan. Si el dividendo es negativo y el divisor es positivo, entonces las definiciones piso y euclidiana concuerdan. Si tanto el dividendo como el divisor son negativos, entonces las definiciones truncada y mínima concuerdan.
Como lo describe Leijen,
Boute sostiene que la división euclidiana es superior a las demás en términos de regularidad y propiedades matemáticas útiles, aunque la división suelo, promovida por Knuth, también es una buena definición. A pesar de su uso generalizado, se ha demostrado que la división truncada es inferior a las otras definiciones.
— Daan Leijen, División y módulo para informáticos [5]
Sin embargo, la división truncada satisface la identidad . [6]
Algunas calculadoras tienen un botón de función mod() y muchos lenguajes de programación tienen una función similar, expresada como mod( a , n ) , por ejemplo. Algunos también admiten expresiones que utilizan "%", "mod" o "Mod" como operador de módulo o resto , como a % n
o a mod n
.
Para entornos que carecen de una función similar, se puede utilizar cualquiera de las tres definiciones anteriores.
Cuando el resultado de una operación de módulo tiene el signo del dividendo (definición truncada), puede dar lugar a errores sorprendentes.
Por ejemplo, para probar si un número entero es impar , uno podría inclinarse por probar si el resto entre 2 es igual a 1:
bool is_odd ( int n ) { retorno n % 2 == 1 ; }
Pero en un lenguaje donde el módulo tiene el signo del dividendo, eso es incorrecto, porque cuando n (el dividendo) es negativo e impar, n mod 2 devuelve −1 y la función devuelve falso.
Una alternativa correcta es probar que el resto no es 0 (porque el resto 0 es el mismo independientemente de los signos):
bool is_odd ( int n ) { retorno n % 2 != 0 ; }
Otra alternativa es utilizar el hecho de que para cualquier número impar, el resto puede ser 1 o −1:
bool is_odd ( int n ) { retorno n % 2 == 1 || norte % 2 == -1 ; }
Una alternativa más sencilla es tratar el resultado de n % 2 como si fuera un valor booleano, donde cualquier valor distinto de cero es verdadero:
bool is_odd ( int n ) { retorno n % 2 ; }
Las operaciones de módulo podrían implementarse de manera que cada vez se calcule una división con un resto. Para casos especiales, en algunos hardware, existen alternativas más rápidas. Por ejemplo, el módulo de potencias de 2 se puede expresar alternativamente como una operación AND bit a bit (asumiendo que x es un entero positivo o usando una definición que no se trunca):
x % 2n == x & (2n - 1)
Ejemplos:
x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
En dispositivos y software que implementan operaciones bit a bit de manera más eficiente que el módulo, estas formas alternativas pueden resultar en cálculos más rápidos. [7]
Las optimizaciones del compilador pueden reconocer expresiones de la forma expression % constant
donde constant
es una potencia de dos e implementarlas automáticamente como expression & (constant-1)
, lo que permite al programador escribir código más claro sin comprometer el rendimiento. Esta optimización simple no es posible para lenguajes en los que el resultado de la operación de módulo tiene el signo del dividendo (incluido C ), a menos que el dividendo sea de tipo entero sin signo . Esto se debe a que, si el dividendo es negativo, el módulo será negativo, mientras que expression & (constant-1)
siempre será positivo. Para estos lenguajes, se debe utilizar la equivalencia, expresada mediante operaciones bit a bit OR, NOT y AND.x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)
También existen optimizaciones para operaciones generales de módulo constante calculando primero la división utilizando la optimización del divisor constante .
Algunas operaciones de módulo se pueden factorizar o expandir de manera similar a otras operaciones matemáticas. Esto puede resultar útil en pruebas de criptografía , como el intercambio de claves Diffie-Hellman . Las propiedades que implican multiplicación, división y exponenciación generalmente requieren que ayn sean números enteros.
Además, muchos sistemas informáticos ofrecen una divmod
funcionalidad que genera el cociente y el resto al mismo tiempo. Los ejemplos incluyen las instrucciones de la arquitectura x86IDIV
, la función del lenguaje de programación C div()
y la función de Pythondivmod()
.
A veces es útil que el resultado de un módulo n no se encuentre entre 0 y n − 1 , sino entre algún número d y d + n − 1 . En ese caso, d se llama desplazamiento y d = 1 es particularmente común.
No parece haber una notación estándar para esta operación, así que usemos tentativamente un mod d n . Tenemos así la siguiente definición: [57] x = a mod d n en el caso de que d ≤ x ≤ d + n − 1 y x mod n = a mod n . Claramente, la operación de módulo habitual corresponde al desplazamiento cero: a mod n = a mod 0 n .
La operación del módulo con compensación está relacionada con la función de piso de la siguiente manera:
Para ver esto, vamos . Primero demostramos que x mod n = a mod n . En general, es cierto que ( a + bn ) mod n = a mod n para todos los números enteros b ; por tanto, esto es cierto también en el caso particular cuando ; pero eso significa eso , que es lo que queríamos demostrar. Queda por demostrar que d ≤ x ≤ d + n − 1 . Sean k y r los números enteros tales que a − d = kn + r con 0 ≤ r ≤ n − 1 (ver división euclidiana ). Entonces , así . Ahora tomamos 0 ≤ r ≤ n − 1 y sumamos d a ambos lados, obteniendo d ≤ d + r ≤ d + n − 1 . Pero hemos visto que x = d + r , así que hemos terminado.
El módulo con desplazamiento a mod d n se implementa en Mathematica como Mod[a, n, d]
. [57]
A pesar de la elegancia matemática de la división piso de Knuth y la división euclidiana, generalmente es mucho más común encontrar un módulo truncado basado en división en los lenguajes de programación. Leijen proporciona los siguientes algoritmos para calcular las dos divisiones dada una división entera truncada: [5]
/* divmod euclidiano y de suelo, al estilo de ldiv() de C */ typedef struct { /* Esta estructura es parte de C stdlib.h, pero se reproduce aquí para mayor claridad */ long int quot ; largo int rem ; } ldiv_t ; /* División euclidiana */ inline ldiv_t ldivE ( long numer , long denom ) { /* Los lenguajes C99 y C++11 definen ambos como truncados. */ long q = número / denominación ; long r = numer % denominación ; si ( r < 0 ) { si ( denom > 0 ) { q = q - 1 ; r = r + denominación ; } más { q = q + 1 ; r = r - denominación ; } } retorno ( ldiv_t ){. quot = q , . rem = r }; } /* División con piso */ inline ldiv_t ldivF ( número largo , denominación larga ) { long q = numer / denom ; long r = numer % denominación ; if (( r > 0 && denom < 0 ) || ( r < 0 && denom > 0 )) { q = q - 1 ; r = r + denominación ; } devolver ( ldiv_t ){. quot = q , . rem = r }; }
En ambos casos, el resto se puede calcular independientemente del cociente, pero no al revés. Las operaciones se combinan aquí para ahorrar espacio en la pantalla, ya que las ramas lógicas son las mismas.
α|ω
calcula el resto al dividir por .ω
α
%
truncamiento. [9] Los estándares anteriores dejan el comportamiento definido por la implementación. [10]div
y mod
no obedecen a la identidad de división de D = d · ( D / d ) + D % d y, por lo tanto, están fundamentalmente rotas.el operador binario % produce el resto de la división de la primera expresión por la segunda. .... Si ambos operandos no son negativos, entonces el resto no es negativo; si no, el signo del resto está definido por la implementación
La función
fmod
devuelve el valor
x - i * y
, para algún número entero
i
tal que, si
y
es distinto de cero, el resultado tiene el mismo signo que
x
y magnitud menor que la magnitud de
y
.
{{cite book}}
: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace ){{cite book}}
: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )X módulo Y, es decir, XY*INT(X/Y).
La función restante, es decir, XY*IP(X/Y).
Si ambos operandos no son negativos, el resto no es negativo. Los resultados no están definidos si uno o ambos operandos son negativos.
El operador % se define solo en los casos en los que ambos lados son positivos o ambos lados son negativos. A diferencia de C, también opera con tipos de datos de punto flotante, así como con números enteros.