stringtranslate.com

módulo

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 evaluarí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.

Variantes de la definición.

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: ocurren 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 las ecuaciones (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 .

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, la división truncada resulta ser 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]

Notación

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 % no a mod n.

Para entornos que carecen de una función similar, se puede utilizar cualquiera de las tres definiciones anteriores.

Errores comunes

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

Problemas de desempeño

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 % constantdonde constantes 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 .

Propiedades (identidades)

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 . Algunas de estas propiedades [ ¿cuáles? ] requieren que a y n sean números enteros.

En lenguajes de programación

Además, muchos sistemas informáticos ofrecen una divmodfuncionalidad que genera el cociente y el resto al mismo tiempo. Los ejemplos incluyen las instrucciones de la arquitectura x86IDIV , la div()función del lenguaje de programación C y la función de Pythondivmod() .

Generalizaciones

Módulo con compensación

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: [56] x = a mod d n en el caso de que dxd + 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 dxd + n − 1 . Sean k y r los números enteros tales que ad = kn + r con 0 ≤ rn − 1 (ver división euclidiana ). Entonces , así . Ahora tomamos 0 ≤ rn − 1 y sumamos d a ambos lados, obteniendo dd + rd + 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] . [56]

Implementación de otras definiciones de módulo mediante truncamiento

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 ; } } devolver ( 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.

Ver también

Notas

  1. ^ Matemáticamente, estas dos opciones son solo dos del infinito número de opciones disponibles para la desigualdad satisfecha por un resto .
  2. ^ ab El orden de los argumentos se invierte, es decir, α|ωcalcula el resto al dividir por .ωα
  3. ^ C99 y C++11 definen el comportamiento de %truncamiento. [9] Los estándares anteriores dejan el comportamiento definido por la implementación. [10]
  4. ^ El divisor debe ser positivo; de lo contrario, no está definido.
  5. ^ Como lo analizó Boute, las definiciones de ISO Pascal divy modno obedecen a la identidad de división de D = d · ( D / d ) + D  % d y, por lo tanto, están fundamentalmente rotas.
  6. ^ Perl suele utilizar un operador de módulo aritmético que es independiente de la máquina. Para ejemplos y excepciones, consulte la documentación de Perl sobre operadores multiplicativos. [42]

Referencias

  1. ^ Weisstein, Eric W. "Congruencia". mathworld.wolfram.com . Consultado el 27 de agosto de 2020 .
  2. ^ Caldwell, Chris. "residuo". Primer glosario . Consultado el 27 de agosto de 2020 .
  3. ^ Knuth, Donald. E. (1972). El arte de la programación informática . Addison-Wesley.
  4. ^ Boute, Raymond T. (abril de 1992). "La definición euclidiana de las funciones div y mod". Transacciones ACM sobre lenguajes y sistemas de programación . ACM Press (Nueva York, NY, EE. UU.). 14 (2): 127-144. doi :10.1145/128861.128862. hdl : 1854/LU-314490 . S2CID  8321674.
  5. ^ ab Leijen, Daan (3 de diciembre de 2001). «División y Módulo para Informáticos» (PDF) . Consultado el 25 de diciembre de 2014 .
  6. ^ Peterson, Doctor (5 de julio de 2001). "Función Mod y números negativos". Foro de matemáticas: pregúntele al Dr. Math . Archivado desde el original el 22 de octubre de 2019 . Consultado el 22 de octubre de 2019 .
  7. ^ Horvath, Adam (5 de julio de 2012). "Operación de módulo y división más rápida: la potencia de dos".
  8. ^ ab "ISO/IEC 8652:2012 - Tecnología de la información - Lenguajes de programación - Ada". ISO , CEI . 2012. seg. 4.5.5 Operadores multiplicadores. {{cite journal}}: Citar diario requiere |journal=( ayuda )
  9. ^ "Especificación C99 (ISO/IEC 9899:TC2)" (PDF) . 2005-05-06. segundo. 6.5.5 Operadores multiplicativos . Consultado el 16 de agosto de 2018 .
  10. ^ "ISO/IEC 14882:2003: Lenguajes de programación - C++". Organización Internacional de Normalización (ISO), Comisión Electrotécnica Internacional (IEC). 2003, seg. 5.6.4. 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 {{cite journal}}: Citar diario requiere |journal=( ayuda )
  11. ^ "ISO/IEC 9899:1990: Lenguajes de programación - C". ISO , CEI . 1990. seg. 7.5.6.4. 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 journal}}: Citar diario requiere |journal=( ayuda )
  12. ^ ab dotnet-bot. "Método (Sistema) Math.IEEERemainder (Doble, Doble)". aprender.microsoft.com . Consultado el 4 de octubre de 2022 .
  13. ^ "clojure.core - Documentación de la API de Clojure v1.10.3". clojure.github.io . Consultado el 16 de marzo de 2022 .
  14. ^ "clojure.core - Documentación de la API de Clojure v1.10.3". clojure.github.io . Consultado el 16 de marzo de 2022 .
  15. ^ ab ISO/IEC JTC 1/SC 22/WG 4 (enero de 2023). ISO/IEC 1989:2023 – Lenguaje de programación COBOL . YO ASI .{{cite book}}: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )
  16. ^ Operadores de CoffeeScript
  17. ^ ISO/IEC JTC 1/SC 22 (febrero de 2012). ISO/IEC 23271:2012 — Tecnología de la información — Infraestructura de lenguaje común (CLI). YO ASI . §§ III.3.55–56.{{cite book}}: Mantenimiento CS1: nombres numéricos: lista de autores ( enlace )
  18. ^ "Expresiones - Lenguaje de programación D". dlang.org . Consultado el 1 de junio de 2021 .
  19. ^ "Método operador % - clase num - biblioteca dart:core - API Dart". api.dart.dev . Consultado el 1 de junio de 2021 .
  20. ^ "método restante - clase num - biblioteca dart:core - API de Dart". api.dart.dev . Consultado el 1 de junio de 2021 .
  21. ^ "Núcleo - Elixir v1.11.3". hexdocs.pm . Consultado el 28 de enero de 2021 .
  22. ^ "Entero - Elixir v1.11.3". hexdocs.pm . Consultado el 28 de enero de 2021 .
  23. ^ "Conceptos básicos: núcleo 1.0.5". paquete.elm-lang.org . Consultado el 16 de marzo de 2022 .
  24. ^ "Conceptos básicos: núcleo 1.0.5". paquete.elm-lang.org . Consultado el 16 de marzo de 2022 .
  25. ^ "Erlang - matemáticas". erlang.org . Consultado el 1 de junio de 2021 .
  26. ^ ANSI (28 de enero de 1987). Lenguajes de programación: BÁSICO completo. Nueva York: Instituto Nacional Estadounidense de Estándares. § 5.4.4. X módulo Y, es decir, XY*INT(X/Y).
  27. ^ ANSI (28 de enero de 1987). Lenguajes de programación: BÁSICO completo. Nueva York: Instituto Nacional Estadounidense de Estándares. § 5.4.4. La función restante, es decir, XY*IP(X/Y).
  28. ^ "Especificación del lenguaje GLSL, versión 4.50.7" (PDF) . sección 5.9 Expresiones. Si ambos operandos no son negativos, el resto no es negativo. Los resultados no están definidos si uno o ambos operandos son negativos.
  29. ^ "Especificación del lenguaje GLSL, versión 4.50.7" (PDF) . sección 8.3 Funciones comunes.
  30. ^ "La especificación del lenguaje de programación Go: el lenguaje de programación Go". ir.dev . Consultado el 28 de febrero de 2022 .
  31. ^ "paquete de matemáticas - matemáticas - pkg.go.dev". pkg.go.dev . Consultado el 28 de febrero de 2022 .
  32. ^ "paquete grande - math/big - pkg.go.dev". pkg.go.dev . Consultado el 28 de febrero de 2022 .
  33. ^ ab "6 tipos y clases predefinidos". www.haskell.org . Consultado el 22 de mayo de 2022 .
  34. ^ "Operadores". Microsoft . Consultado el 19 de julio de 2021 . 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.
  35. ^ "Matemáticas · El lenguaje Julia". docs.julialang.org . Consultado el 20 de noviembre de 2021 .
  36. ^ "Matemáticas · El lenguaje Julia". docs.julialang.org . Consultado el 20 de noviembre de 2021 .
  37. ^ "rem - Lenguaje de programación Kotlin". Kotlin . Consultado el 5 de mayo de 2021 .
  38. ^ "mod - Lenguaje de programación Kotlin". Kotlin . Consultado el 5 de mayo de 2021 .
  39. ^ "Capítulo 3: El lenguaje NASM". NASM: la versión 2.15.05 del ensamblador de red .
  40. ^ "Biblioteca OCaml: Stdlib". ocaml.org . Consultado el 19 de febrero de 2022 .
  41. ^ "Biblioteca OCaml: Stdlib". ocaml.org . Consultado el 19 de febrero de 2022 .
  42. ^ Documentación Perl
  43. ^ "PHP: Operadores aritméticos - Manual". www.php.net . Consultado el 20 de noviembre de 2021 .
  44. ^ "PHP: fmod-Manual". www.php.net . Consultado el 20 de noviembre de 2021 .
  45. ^ "Anillo euclidiano".
  46. ^ Escritor cuántico. "Expresiones". docs.microsoft.com . Consultado el 11 de julio de 2018 .
  47. ^ "R: operadores aritméticos". search.r-project.org . Consultado el 24 de diciembre de 2022 .
  48. ^ "F32 - Óxido".
  49. ^ ab r6rs.org
  50. ^ "Lenguaje de comando de Shell". pubs.opengroup.org . Consultado el 5 de febrero de 2021 .
  51. ^ "Documentación para desarrolladores de Apple". desarrollador.apple.com . Consultado el 20 de noviembre de 2021 .
  52. ^ "Documentación para desarrolladores de Apple". desarrollador.apple.com . Consultado el 20 de noviembre de 2021 .
  53. ^ "Documentación para desarrolladores de Apple". desarrollador.apple.com . Consultado el 20 de noviembre de 2021 .
  54. ^ ab Rossberg, Andreas, ed. (19 de abril de 2022). "Especificación principal de WebAssembly: versión 2.0". Consorcio Mundial de la red . § 4.3.2 Operaciones con números enteros.
  55. ^ "Documentación en Zig". Lenguaje de programación Zig . Consultado el 18 de diciembre de 2022 .
  56. ^ ab "Modificación". Centro de documentación de sistemas y lenguaje Wolfram . Investigación Wolfram . 2020 . Consultado el 8 de abril de 2020 .

enlaces externos