¿Por qué C ++ genera números negativos cuando se usa módulo?

Matemáticas :

Si tienes una ecuación como esta:

x = 3 mod 7 

x podría ser … -4, 3, 10, 17, …, o más en general:

 x = 3 + k * 7 

donde k puede ser cualquier número entero. No sé de una operación de módulo definida para matemáticas, pero el anillo de factores sí lo es.

Python :

En Python, siempre obtendrá valores no negativos cuando use % con m positivo:

 #!/usr/bin/python # -*- coding: utf-8 -*- m = 7 for i in xrange(-8, 10 + 1): print(i % 7) 

Resultados en:

 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 

C ++:

 #include  using namespace std; int main(){ int m = 7; for(int i=-8; i <= 10; i++) { cout << (i % m) << endl; } return 0; } 

Se producirá:

 -1 0 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 0 1 2 3 

ISO / IEC 14882: 2003 (E) – 5.6 Operadores multiplicadores:

El operador binario produce el cociente, y el operador binario% produce el rest de la división de la primera expresión por el segundo. Si el segundo operando de / o% es cero, el comportamiento no está definido; de lo contrario (a / b) * b + a% b es igual a a. Si ambos operandos son no negativos, el rest no es negativo; si no, el signo del rest está definido por la implementación 74) .

y

74) Según el trabajo en curso para la revisión de ISO C, el algoritmo preferido para la división de enteros sigue las reglas definidas en el estándar ISO Fortran, ISO / IEC 1539: 1991, en el que el cociente siempre se redondea hacia cero.

Fuente: ISO / IEC 14882: 2003 (E)

(No pude encontrar una versión gratuita de ISO/IEC 1539:1991 ¿Alguien sabe de dónde sacarla?)

La operación parece definirse así:

enter image description here

Pregunta :

¿Tiene sentido definirlo así?

¿Cuáles son los argumentos para esta especificación? ¿Hay algún lugar donde las personas que crean dichos estándares lo discutan? ¿Dónde puedo leer algo sobre las razones por las que decidieron hacerlo de esta manera?

La mayoría de las veces, cuando uso modulo, quiero acceder a los elementos de una estructura de datos. En este caso, tengo que asegurarme de que el mod devuelva un valor no negativo. Entonces, para este caso, sería bueno que el mod siempre devuelva un valor no negativo. (Otro uso es el algoritmo euclidiano . Como puedes hacer que ambos números sean positivos antes de usar este algoritmo, el signo del módulo sería importante).

Material adicional :

Consulte Wikipedia para obtener una lista larga de lo que Modulo hace en diferentes idiomas.

En x86 (y otras architectures de procesador), la división y el módulo enteros se llevan a cabo mediante una sola operación, idiv ( div para valores sin signo), que produce tanto cociente como rest (para argumentos de tamaño de palabra, en AX y DX respectivamente). Esto se usa en la función de biblioteca C divmod , que el comstackdor puede optimizar a una sola instrucción.

La división entera respeta dos reglas:

  • Los cocientes no enteros se redondean hacia cero; y
  • la ecuación dividend = quotient*divisor + remainder se satisface con los resultados.

En consecuencia, al dividir un número negativo por un número positivo, el cociente será negativo (o cero).

Entonces, este comportamiento puede verse como el resultado de una cadena de decisiones locales:

  • El diseño del conjunto de instrucciones del procesador se optimiza para el caso común (división) sobre el caso menos común (módulo);
  • La consistencia (redondeo hacia cero y respetando la ecuación de división) es preferible a la corrección matemática;
  • C prefiere la eficiencia y de manera simple (especialmente dada la tendencia a ver a C como un “ensamblador de alto nivel”); y
  • C ++ prefiere la compatibilidad con C.

¿Cuáles son los argumentos para esta especificación?

Uno de los objectives de diseño de C ++ es hacer un mapa eficiente del hardware. Si el hardware subyacente implementa la división de una manera que produce residuos negativos, eso es lo que obtendrá si usa % en C ++. Eso es todo lo que hay realmente.

¿Hay algún lugar donde las personas que crean dichos estándares lo discutan?

Encontrará discusiones interesantes sobre comp.lang.c ++. Moderado y, en menor medida, comp.lang.c ++

En el pasado, alguien que diseñaba el conjunto de instrucciones x86 decidió que era correcto y bueno redondear la división entera hacia cero en lugar de redondear hacia abajo. (Que las pulgas de mil camellos aniden en la barba de su madre.) Para mantener cierta apariencia matemática correcta, el operador REM, que se pronuncia “rest”, tuvo que comportarse como corresponde. NO lea esto: https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm

Te lo adverti. Más tarde, alguien que hace la especificación C decidió que sería conforme para un comstackdor hacerlo de la manera correcta o x86. Luego, un comité que hace las especificaciones de C ++ decidió hacerlo de la manera C. Luego, aún más tarde, después de publicar esta pregunta, un comité de C ++ decidió estandarizar en el camino equivocado. Ahora estamos atrapados con eso. Muchos progtwigdores han escrito la siguiente función o algo así. Probablemente lo haya hecho al menos una docena de veces.

  inline int mod(int a, int b) {int ret = a%b; return ret>=0? ret: ret+b; } 

Ahí va tu eficiencia.

En estos días utilizo esencialmente lo siguiente, con algunos elementos de type_traits arrojados. (Gracias a Clearer por un comentario que me dio una idea para una mejora usando C ++ de los últimos días. Vea a continuación).

 template inline T mod(T a, T b) { assert(b > 0); T ret = a%b; return (ret>=0)?(ret):(ret+b); } template<> inline unsigned mod(unsigned a, unsigned b) { assert(b > 0); return a % b; } 

Verdadero hecho: presioné al comité de estándares de Pascal para que hiciera modificaciones de la manera correcta hasta que cedieran. Para mi horror, hicieron una división entera de la manera incorrecta. Entonces ni siquiera coinciden.

EDITAR: Clearer me dio una idea. Estoy trabajando en uno nuevo.

 #include  template inline T1 mod(T1 a, T2 b) { assert(b > 0); T1 ret = a % b; if constexpr ( std::is_unsigned_v) { return ret; } else { return (ret >= 0) ? (ret) : (ret + b); } }