Opération Modulo avec des nombres négatifs

Dans le programme ca j’essayais les opérations ci-dessous (juste pour vérifier le comportement)

x = 5 % (-3); y = (-5) % (3); z = (-5) % (-3); printf("%d ,%d ,%d", x, y, z); 

m’a donné comme résultat (2, -2 , -2) dans gcc. Je m’attendais à un résultat positif à chaque fois. Un module peut-il être négatif? Quelqu’un peut-il expliquer ce comportement?

C99 exige que lorsque a/b est représentable:

(a/b) * b + a%b doit être égal a

Cela a du sens, logiquement. Droite?

Voyons ce que cela conduit à:


Exemple A. 5/(-3) est -1

=> (-1) * (-3) + 5%(-3) = 5

Cela ne peut arriver que si 5%(-3) est 2.


Exemple B. (-5)/3 est -1

=> (-1) * 3 + (-5)%3 = -5

Cela ne peut arriver que si (-5)%3 est -2

L’opérateur % en C n’est pas l’opérateur modulo mais l’opérateur restant .

Les opérateurs modulo et rest diffèrent en ce qui concerne les valeurs négatives.

Avec un opérateur restant, le signe du résultat est le même que le signe du dividende tandis qu’avec un opérateur modulo, le signe du résultat est identique au diviseur.

C définit l’opération % pour a % b comme:

  a == (a / b * b) + a % b 

avec / la division entière avec troncature vers 0 . C’est la troncature faite vers 0 (et non vers l’inifinité négative) qui définit le % comme un opérateur restant plutôt qu’un opérateur modulo.

Basé sur la spécification C99: a = (a / b) * b + a % b

Nous pouvons écrire une fonction pour calculer (a % b) = a - (a / b) * b !

 int remainder(int a, int b) { return a - (a / b) * b; } 

Pour un fonctionnement modulo, nous pouvons avoir la fonction suivante (en supposant que b> 0)

 int mod(int a, int b) { int r = a % b; return r < 0 ? r + b : r; } 

Ma conclusion est que (un% b) en C est un opérateur restant et non un opérateur modulo.

Je ne pense pas qu’il soit nécessaire de vérifier si le nombre est négatif. La fonction générale la plus simple pour trouver le modulo positif serait la suivante: cela fonctionnerait à la fois sur les valeurs positives et négatives de x.

 int modulo(int x,int N){ return (x % N + N) %N; } 

Les autres réponses ont expliqué en C99 ou plus tard, la division des entiers impliquant des opérandes négatifs est toujours tronquée vers zéro .

Notez que, en C89 , le résultat arrondi à la hausse ou à la baisse est défini par la mise en œuvre. Parce que (a/b) * b + a%b est égal à a dans toutes les normes, le résultat de % impliquant des opérandes négatifs est également défini dans C89.

Le résultat de l’opération Modulo dépend du signe du numérateur, et vous obtenez donc -2 pour y et z

Voici la référence

http://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_14.html

Division entière

Cette section décrit les fonctions permettant d’effectuer une division entière. Ces fonctions sont redondantes dans la bibliothèque GNU C, car dans GNU C, l’opérateur «/» arrondit toujours vers zéro. Mais dans d’autres implémentations C, ‘/’ peut arrondir différemment avec des arguments négatifs. div et ldiv sont utiles car elles spécifient comment arrondir le quotient: vers zéro. Le rest a le même signe que le numérateur.

En mathématiques, d’où proviennent ces conventions, il n’y a pas d’affirmation que l’arithmétique modulo devrait donner un résultat positif.

Par exemple.

1 mod 5 = 1, mais il peut aussi être égal à -4. C’est-à-dire que 1/5 donne un rest 1 de 0 ou -4 à partir de 5. (Les deux facteurs de 5)

De même, -1 mod 5 = -1, mais il peut aussi être égal à 4. C’est-à-dire que -1/5 donne un rest -1 à partir de 0 ou 4 à partir de -5. (Deux facteurs de 5)

Pour en savoir plus sur les classes d’équivalence en mathématiques.

L’opérateur de module donne le rest. L’opérateur de module en c prend généralement le signe du numérateur

  1. x = 5% (-3) – ici le numérateur est positif, donc 2
  2. y = (-5)% (3) – ici le numérateur est négatif, donc -2
  3. z = (-5)% (-3) – ici le numérateur est négatif d’où il résulte -2

De plus, l’opérateur modulus (rest) ne peut être utilisé qu’avec un type entier et ne peut pas être utilisé avec des virgules flottantes.

L’opérateur modulo est comme l’opérateur mod lorsque le nombre est positif, mais différent si le nombre est négatif.

Plusieurs fois dans les problèmes, on nous demande de donner la réponse modulo 10 ^ 9 + 7.

Laissez la réponse (avant d’utiliser modulo) être notée par «a».

Règle simple et directe-

si a est positif , alors un modulo 10 ^ 9 + 7 = a% (10 ^ 9 + 7)

si a est négatif , alors un modulo 10 ^ 9 + 7 = (a% (10 ^ 9 + 7)) + (10 ^ 9 + 7)

Si, dans de tels problèmes, nous trouvons qu’une étape quelconque de la boucle peut calculer une valeur qui est en dehors de la plage entière (si nous utilisons des entiers), alors nous pouvons utiliser l’opérateur modulo dans cette étape elle-même. La réponse finale sera comme si nous n’avions utilisé l’opérateur modulo qu’une seule fois.

C’est parce que (a * b)% c = ((a% c) (b% c))% c Même chose pour l’addition et la soustraction.

Conformément à la norme C99 , section 6.5.5 Opérateurs multiplicatifs , les éléments suivants sont requirejs:

 (a / b) * b + a % b = a 

Conclusion

Selon C99, le signe du résultat d’une opération restante est le même que celui du dividende.

Voyons quelques exemples ( dividend / divisor ):

Quand seul le dividende est négatif

 (-3 / 2) * 2 + -3 % 2 = -3 (-3 / 2) * 2 = -2 (-3 % 2) must be -1 

Lorsque seul le diviseur est négatif

 (3 / -2) * -2 + 3 % -2 = 3 (3 / -2) * -2 = 2 (3 % -2) must be 1 

Lorsque le diviseur et le dividende sont tous deux négatifs

 (-3 / -2) * -2 + -3 % -2 = -3 (-3 / -2) * -2 = -2 (-3 % -2) must be -1 

6.5.5 Opérateurs multiplicatifs

Syntaxe

  1. expression multiplicative:
    • cast-expression
    • multiplicative-expression * cast-expression
    • multiplicative-expression / cast-expression
    • multiplicative-expression % cast-expression

Contraintes

  1. Chacun des opérandes doit avoir un type arithmétique. Les opérandes de l’opérateur % doivent avoir un type entier.

Sémantique

  1. Les conversions arithmétiques habituelles sont effectuées sur les opérandes.

  2. Le résultat de l’opérateur binary * est le produit des opérandes.

  3. Le résultat de l’opérateur / est le quotient de la division du premier opérande par le second; le résultat de l’opérateur % est le rest. Dans les deux opérations, si la valeur du deuxième opérande est zéro, le comportement est indéfini.

  4. Lorsque des entiers sont divisés, le résultat de l’opérateur / est le quotient algébrique avec toute partie fractionnaire rejetée [1]. Si le quotient a/b est représentable, l’expression (a/b)*b + a%b doit être égale à a .

[1]: Ceci est souvent appelé “troncature vers zéro”.