Le mod du nombre négatif fait fondre mon cerveau

J’essaie de moduler un nombre entier pour obtenir une position de tableau afin qu’il se boucle. Faire i % arrayLength fonctionne bien pour les nombres positifs mais pour les nombres négatifs, tout se passe mal.

  4 % 3 == 1 3 % 3 == 0 2 % 3 == 2 1 % 3 == 1 0 % 3 == 0 -1 % 3 == -1 -2 % 3 == -2 -3 % 3 == 0 -4 % 3 == -1 

donc j’ai besoin d’une mise en œuvre de

 int GetArrayIndex(int i, int arrayLength) 

tel que

 GetArrayIndex( 4, 3) == 1 GetArrayIndex( 3, 3) == 0 GetArrayIndex( 2, 3) == 2 GetArrayIndex( 1, 3) == 1 GetArrayIndex( 0, 3) == 0 GetArrayIndex(-1, 3) == 2 GetArrayIndex(-2, 3) == 1 GetArrayIndex(-3, 3) == 0 GetArrayIndex(-4, 3) == 2 

J’ai déjà fait ça mais pour une raison quelconque, ça me fait fondre le cerveau aujourd’hui 🙁

J’utilise toujours ma propre fonction de mod , définie comme

 int mod(int x, int m) { return (x%m + m)%m; } 

Bien sûr, si vous ne voulez pas avoir deux appels à l’opération de module, vous pouvez l’écrire comme suit:

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

ou des variantes de ceux-ci.

La raison pour laquelle cela fonctionne est que "x% m" est toujours dans la plage [-m + 1, m-1]. Donc, s'il est négatif, l'append à m le placera dans la plage positive sans changer sa valeur modulo m.

S’il vous plaît noter que l’opérateur% C # et C ++ n’est en fait pas un modulo, c’est le rest. La formule de modulo que vous voulez, dans votre cas, est la suivante:

 float nfmod(float a,float b) { return a - b * floor(a / b); } 

Vous devez recoder ceci en C # (ou C ++) mais c’est comme ça que vous obtenez modulo et pas un rest.

Implémentation sur une seule ligne utilisant % seulement une fois:

 int mod(int k, int n) { return ((k %= n) < 0) ? k+n : k; } 

La réponse de ShreevatsaR ne fonctionnera pas dans tous les cas, même si vous ajoutez “if (m <0) m = -m;", si vous tenez compte des dividendes / diviseurs négatifs.

Par exemple, -12 mod -10 sera 8 et devrait être -2.

L’implémentation suivante fonctionnera pour les dividendes / diviseurs positifs et négatifs et sera conforme aux autres implémentations (à savoir, Java, Python, Ruby, Scala, Scheme, Javascript et Google Calculator):

 internal static class IntExtensions { internal static int Mod(this int a, int n) { if (n == 0) throw new ArgumentOutOfRangeException("n", "(a mod 0) is undefined."); //puts a in the [-n+1, n-1] range using the remainder operator int remainder = a%n; //if the remainder is less than zero, add n to put it in the [0, n-1] range if n is positive //if the remainder is greater than zero, add n to put it in the [n-1, 0] range if n is negative if ((n > 0 && remainder < 0) || (n < 0 && remainder > 0)) return remainder + n; return remainder; } } 

Suite de test utilisant xUnit:

  [Theory] [PropertyData("GetTestData")] public void Mod_ReturnsCorrectModulo(int dividend, int divisor, int expectedMod) { Assert.Equal(expectedMod, dividend.Mod(divisor)); } [Fact] public void Mod_ThrowsException_IfDivisorIsZero() { Assert.Throws(() => 1.Mod(0)); } public static IEnumerable GetTestData { get { yield return new object[] {1, 1, 0}; yield return new object[] {0, 1, 0}; yield return new object[] {2, 10, 2}; yield return new object[] {12, 10, 2}; yield return new object[] {22, 10, 2}; yield return new object[] {-2, 10, 8}; yield return new object[] {-12, 10, 8}; yield return new object[] {-22, 10, 8}; yield return new object[] { 2, -10, -8 }; yield return new object[] { 12, -10, -8 }; yield return new object[] { 22, -10, -8 }; yield return new object[] { -2, -10, -2 }; yield return new object[] { -12, -10, -2 }; yield return new object[] { -22, -10, -2 }; } } 

Pour les développeurs plus sensibles aux performances

 uint wrap(int k, int n) ((uint)k)%n 

Une petite comparaison de performance

 Modulo: 00:00:07.2661827 ((n%x)+x)%x) Cast: 00:00:03.2202334 ((uint)k)%n If: 00:00:13.5378989 ((k %= n) < 0) ? k+n : k 

En ce qui concerne le coût de la performance de la fonte pour ne pas jeter un oeil ici

Ajout d’une certaine compréhension.

Par définition euclidienne, le résultat du mod doit toujours être positif.

Ex:

  int n = 5; int x = -3; int mod(int n, int x) { return ((n%x)+x)%x; } 

Sortie:

  -1 

Ajoutez simplement votre module (arrayLength) au résultat négatif de% et vous irez bien.

J’aime le tour présenté par Peter N Lewis sur ce sujet : “Si n a une scope limitée, alors vous pouvez obtenir le résultat souhaité simplement en ajoutant un multiple constant connu de [le diviseur] qui est supérieur à la valeur absolue du le minimum.”

Donc, si j’ai une valeur d qui est en degrés et je veux prendre

 d % 180f 

et je veux éviter les problèmes si d est négatif, alors je fais juste ça:

 (d + 720f) % 180f 

Cela suppose que, bien que d puisse être négatif, on sait qu’il ne sera jamais plus négatif que -720.

Comparer deux réponses prédominantes

 (x%m + m)%m; 

et

 int r = x%m; return r<0 ? r+m : r; 

Personne n'a mentionné le fait que le premier pouvait lancer une OverflowException tandis que le second ne le ferait pas. Pire encore, avec un contexte non contrôlé par défaut, la première réponse peut renvoyer la mauvaise réponse (voir par exemple mod(int.MaxValue - 1, int.MaxValue) ). Donc, la deuxième réponse semble non seulement plus rapide, mais aussi plus correcte.