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

Question

Matemáticas:

Si usted tiene una ecuación como esta:

x = 3 mod 7 

x podrían 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 se utiliza % con un resultado positivo m:

#!/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++:

salida

#include <iostream> 

using namespace std; 

int main(){ 
    int m = 7; 

    for(int i=-8; i <= 10; i++) { 
     cout << (i % m) << endl; 
    } 

    return 0; 
} 

Will:

-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 multiplicativos:

The binary/operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of/or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined 74).

y

74) According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.

Fuente: ISO/IEC 14882:2003(E)

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

La operación parece definirse así:?

Pregunta:

¿Tiene sentido para definir 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 módulo, 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 Euclidean algorithm. Como podría hacer que ambos números sean positivos antes de usar este algoritmo, el signo del módulo sería importante.)

El material adicional:

Ver Wikipedia para una larga lista de lo que hace de módulo en diferentes idiomas.

Answer 1

en x86 (y otras arquitecturas de procesador), una división de enteros módulo y se llevado a cabo por una sola operación, idiv (div para valores sin signo), que produce el cociente y el resto (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 compilador puede optimizar en una sola instrucción.

división de enteros respeta dos reglas:

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

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

Así que este comportamiento puede ser visto como el resultado de una cadena de decisiones locales:

• Procesador de diseño optimiza el conjunto de instrucciones 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 compatibilidad con C.

Answer 2

What are arguments for this specification?

Uno de los objetivos 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, entonces eso es lo que obtendrá si usa % en C++. Eso es todo lo que hay realmente.

Is there a place where the people who create such standards discuss about it?

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

Answer 3

vuelta en el día, alguien diseñar el conjunto de instrucciones x86 decidió que era correcto y bueno para la división entera redonda 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 "resto", tuvo que comportarse como corresponde. NO lea esto: https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm

Te lo advertí. Más tarde, alguien que hace la especificación C decidió que sería conforme para un compilador 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 programadores 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 su eficacia.

En estos días me utilizan esencialmente los siguientes, con algunas type_traits Stuff arrojados. (Gracias a más claras para un comentario que me dio una idea para una mejora utilizando este último día C++. Ver abajo.)

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

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.

EDIT: Clearer me hizo una idea. Estoy trabajando en uno nuevo.

#include <type_traits> 

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