Pourquoi C ++ génère-t-il des nombres négatifs lors de l’utilisation de modulo?

Maths :

Si vous avez une équation comme celle-ci:

x = 3 mod 7 

x pourrait être … -4, 3, 10, 17, …, ou plus généralement:

 x = 3 + k * 7 

où k peut être n’importe quel entier. Je ne sais pas d’une opération modulo est définie pour les mathématiques, mais le facteur anneau est certainement.

Python :

En Python, vous obtiendrez toujours des valeurs non négatives lorsque vous utilisez % avec un m positif:

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

Résulte 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; } 

Va sortir:

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

ISO / IEC 14882: 2003 (F) – 5.6 Opérateurs multiplicatifs:

L’opérateur binary / donne le quotient et l’opérateur binary% renvoie le rest de la division de la première expression par le second. Si le second opérande de / ou% est nul, le comportement est indéfini. sinon (a / b) * b + a% b est égal à a. Si les deux opérandes ne sont pas négatifs, le rest est non négatif. sinon, le signe du rest est défini par la mise en œuvre 74) .

et

74) Selon les travaux en cours pour la révision de l’ISO C, l’algorithme préféré pour la division entière suit les règles définies dans la norme ISO Fortran, ISO / IEC 1539: 1991, dans laquelle le quotient est toujours arrondi à zéro.

Source: ISO / IEC 14882: 2003 (F)

(Je n’ai pas trouvé de version gratuite de l’ ISO/IEC 1539:1991 Est-ce que quelqu’un sait où l’obtenir?)

L’opération semble être définie comme ceci:

entrer la description de l'image ici

Question :

Est-il judicieux de le définir comme ça?

Quels sont les arguments pour cette spécification? Y a-t-il un endroit où les personnes qui créent de telles normes en discutent? Où puis-je lire quelque chose sur les raisons pour lesquelles ils ont décidé de procéder ainsi?

La plupart du temps, lorsque j’utilise modulo, je souhaite accéder à des éléments d’une structure de données. Dans ce cas, je dois m’assurer que le mod retourne une valeur non négative. Donc, pour ce cas, il serait bon que le mod renvoie toujours une valeur non négative. (Un autre usage est l’ algorithme euclidien . Comme vous pouviez rendre les deux nombres positifs avant d’utiliser cet algorithme, le signe de modulo importerait.)

Matériel supplémentaire :

Voir Wikipedia pour une longue liste de ce que modulo fait dans différentes langues.

Sur x86 (et les autres architectures de processeurs), la division entière et le modulo sont exécutés par une seule opération, idiv ( div pour les valeurs non signées), qui produit à la fois quotient et rest (pour les arguments au format AX et DX ). Ceci est utilisé dans la fonction divmod bibliothèque C, qui peut être optimisée par le compilateur en une seule instruction!

La division entière respecte deux règles:

  • Les quotients non entiers sont arrondis vers zéro; et
  • l’équation dividend = quotient*divisor + remainder est satisfaite par les résultats.

En conséquence, lors de la division d’un nombre négatif par un nombre positif, le quotient sera négatif (ou nul).

Ce comportement peut donc être considéré comme le résultat d’une chaîne de décisions locales:

  • La conception du jeu d’instructions du processeur est optimisée pour le cas commun (division) sur le cas le moins commun (modulo);
  • La cohérence (arrondi vers zéro et respectant l’équation de la division) est préférable à la correction mathématique.
  • C préfère l’efficacité et la simplicité (surtout compte tenu de la tendance à considérer C comme un “assembleur de haut niveau”); et
  • C ++ préfère la compatibilité avec C.

Quels sont les arguments pour cette spécification?

L’un des objectives de conception de C ++ est de mapper efficacement vers le matériel. Si le matériel sous-jacent implémente la division de manière à produire des rests négatifs, vous obtiendrez ce résultat si vous utilisez % en C ++. C’est tout ce qu’il y a à faire.

Y a-t-il un endroit où les personnes qui créent de telles normes en discutent?

Vous trouverez des discussions intéressantes sur comp.lang.c ++. Modérées et, dans une moindre mesure, comp.lang.c ++

Dans le passé, quelqu’un qui concevait le jeu d’instructions x86 a décidé qu’il était bon et bon de diviser la division entière par zéro plutôt que d’arrondir. (Que les puces d’un millier de chameaux nichent dans la barbe de sa mère.) Pour conserver un semblant de justesse mathématique, l’opérateur REM, qui se prononce “rest”, devait se comporter en conséquence. NE PAS lire ceci: https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_73/rzatk/REM.htm

Je t’avais prévenu. Plus tard, quelqu’un faisant la spécification C a décidé qu’il serait conforme pour un compilateur de le faire soit correctement, soit de manière x86. Ensuite, un comité chargé de la spécification C ++ a décidé de le faire de la manière C. Ensuite, après la publication de cette question, un comité C ++ a décidé de standardiser de manière incorrecte. Maintenant, nous sums coincés avec ça. Beaucoup de programmeurs ont écrit la fonction suivante ou quelque chose du genre. Je l’ai probablement fait au moins une douzaine de fois.

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

Il y a votre efficacité.

Ces jours-ci, j’utilise essentiellement ce qui suit, avec des éléments de type_traits. (Merci à Clearer pour un commentaire qui m’a donné une idée d’amélioration avec le C ++ de ce jour. Voir ci-dessous.)

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

Vrai fait: j’ai exercé des pressions sur le comité de normalisation Pascal pour qu’il modifie le processus jusqu’à ce qu’il cède. À ma grande horreur, ils ont fait une division entière dans le mauvais sens. Donc, ils ne correspondent même pas.

EDIT: Clearer m’a donné une idée. Je travaille sur un nouveau.

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