Comment coder un opérateur modulo (%) en C/C++/Obj-C qui gère les nombres négatifs ?

Question

L'une de mes principales détestations des langages dérivés du C (en tant que mathématicien) est que

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

Quelle est la meilleure solution ?

Le C++ offre la possibilité d'utiliser des modèles et de surcharger les opérateurs, mais ces deux éléments sont des eaux troubles pour moi.

Answer 1

Tout d'abord, je voudrais noter que vous ne pouvez même pas compter sur le fait que (-1) % 8 == -1 . la seule chose sur laquelle vous pouvez compter est que (x / y) * y + ( x % y) == x . Cependant, le fait que le reste soit négatif ou non est définie par la mise en œuvre .

Pourquoi utiliser des modèles ici ? Une surcharge pour les ints et les longs ferait l'affaire.

int mod (int a, int b)
{
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

et maintenant vous pouvez l'appeler comme mod(-1,8) et il apparaîtra comme étant 7.

Edit : J'ai trouvé un bug dans mon code. Il ne fonctionne pas si b est négatif. Donc je pense que ceci est mieux :

int mod (int a, int b)
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return -mod(-a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

Référence : C++03 paragraphe 5.6 clause 4 :

L'opérateur binaire / donne le quotient, et l'opérateur binaire % donne le reste de la division de la première expression par la seconde. Si le second opérande de / ou de % est égal à zéro, le comportement est indéfini ; sinon, (a/b)*b + a%b est égal à a. Si les deux opérandes sont non négatifs, le reste est non négatif ; sinon, le signe du reste est défini par l'implémentation. .

Answer 2

Voici une fonction C qui traite les valeurs entières OU fractionnaires positives OU négatives pour LES DEUX OPÉRATIONS

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

C'est certainement la solution la plus élégante d'un point de vue mathématique. Cependant, je ne suis pas sûr qu'elle soit robuste dans la gestion des entiers. Parfois, des erreurs de virgule flottante se glissent lors de la conversion int -> fp -> int.

J'utilise ce code pour les s non-int, et une fonction séparée pour les int.

NOTE : il faut piéger N = 0 !

Code du testeur :

#include <math.h>
#include <stdio.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! \n\n", fmodf(-10.2, 2.0));

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

(Note : Vous pouvez compiler et exécuter le programme directement à partir de CodePad : http://codepad.org/UOgEqAMA )

Sortie :

fmodf(-10.2, 2.0) = -0.20 == FAIL !

10,2 mod 2,0 = 0,2
10,2 mod -2,0 = -1,8
-10,2 mod 2,0 = 1,8
-10,2 mod -2,0 = -0,2

Answer 3

Pour les nombres entiers, c'est simple. Il suffit de faire

(((x < 0) ? ((x % N) + N) : x) % N)

où je suppose que N est positif et représentable dans le type de x . Votre compilateur préféré devrait être capable d'optimiser cette opération, de telle sorte qu'elle se termine par une seule opération de modulation en assembleur.

Answer 4

La meilleure solution ¹ pour un mathématicien est d'utiliser Python.

La surcharge d'opérateurs en C++ n'a pas grand-chose à voir avec cela. Vous ne pouvez pas surcharger les opérateurs pour les types intégrés. Ce que vous voulez, c'est simplement une fonction. Bien sûr, vous pouvez utiliser la modélisation C++ pour implémenter cette fonction pour tous les types pertinents avec un seul morceau de code.

La bibliothèque C standard fournit fmod si je me souviens bien du nom, pour les types à virgule flottante.

Pour les entiers, vous pouvez définir un modèle de fonction C++ qui renvoie toujours le reste non négatif (correspondant à la division euclidienne) comme ...

#include <stdlib.h>  // abs

template< class Integer >
auto mod( Integer a, Integer b )
    -> Integer
{
    Integer const r = a%b;
    return (r < 0? r + abs( b ) : r);
}

... et écrire simplement mod(a, b) au lieu de a%b .

Ici, le type Integer doit être un type d'entier signé.

Si vous voulez le comportement mathématique commun où le signe du reste est le même que le signe du diviseur, vous pouvez faire par ex.

template< class Integer >
auto floor_div( Integer const a, Integer const b )
    -> Integer
{
    bool const a_is_negative = (a < 0);
    bool const b_is_negative = (b < 0);
    bool const change_sign  = (a_is_negative != b_is_negative);

    Integer const abs_b         = abs( b );
    Integer const abs_a_plus    = abs( a ) + (change_sign? abs_b - 1 : 0);

    Integer const quot = abs_a_plus / abs_b;
    return (change_sign? -quot : quot);
}

template< class Integer >
auto floor_mod( Integer const a, Integer const b )
    -> Integer
{ return a - b*floor_div( a, b ); }

avec la même contrainte sur Integer que c'est un type signé.

---

¹ Parce que la division entière de Python arrondit vers l'infini négatif.

Answer 5

Oh, je déteste % design pour ça aussi....

Vous pouvez convertir le dividende en non signé de la manière suivante :

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

où le décalage est le plus proche du multiple (-INT_MIN) du module, donc l'ajouter et le soustraire ne changera pas le modulo. Notez qu'il a un type non signé et que le résultat sera un entier. Malheureusement, elle ne peut pas convertir correctement les valeurs INT_MIN...(-offset-1) car elles provoquent un débordement arifmétique. Mais cette méthode a l'avantage de n'avoir qu'une seule opération arithmétique supplémentaire par opération (et pas de conditionnel) lorsqu'on travaille avec un diviseur constant, donc elle est utilisable dans des applications de type DSP.

Il y a un cas spécial, où le diviseur est 2. N (puissance entière de deux), pour laquelle le modulo peut être calculé à l'aide d'une arithmétique simple et d'une logique bit à bit, comme suit

dividend&(divider-1)

par exemple

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

Une méthode plus courante et moins délicate consiste à obtenir le modulo en utilisant cette fonction (fonctionne uniquement avec un diviseur positif) :

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

Cela corrige juste le résultat s'il est négatif.

Vous pouvez aussi tricher :

(p%q + q)%q

Il est très court mais utilise deux %-s qui sont généralement lents.