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

L'un de mes animaux de compagnie déteste les 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?

C ++ permet la possibilité de surcharger les modèles et les opérateurs, mais ces deux éléments sont pour moi des eaux troubles. exemples reçus avec gratitude.

Tout d'abord, j'aimerais noter que vous ne pouvez même pas vous fier à cela (-1) % 8 == -1. la seule chose sur laquelle vous pouvez compter, c'est cela (x / y) * y + ( x % y) == x. Cependant, le fait que le reste soit négatif ou non est défini par l'implémentation .

Maintenant, pourquoi utiliser des modèles ici? Une surcharge pour les entiers 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 semblera être 7.

Edit: j'ai trouvé un bug dans mon code. Cela ne fonctionnera pas si b est négatif. Donc je pense que c'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 deuxième opérande de / ou% est égal à zéro, le comportement n'est pas dé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 .

Voici une fonction C qui gère les entiers positifs OU négatifs OU les valeurs fractionnaires pour LES DEUX OPÉRANDES

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

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

J'utilise ce code pour les non-int et une fonction distincte pour int.

REMARQUE: besoin de 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;
}

(Remarque: vous pouvez le compiler et l'exécuter directement à partir de CodePad: http://codepad.org/UOgEqAMA )

Production:

fmodf (-10,2, 2,0) = -0,20 == ÉCHEC!

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

Je viens de remarquer que Bjarne Stroustrup étiquette %comme l' opérateur de reste , pas l'opérateur modulo.

Je parierais que c'est son nom officiel dans les spécifications ANSI C & C ++, et que l'abus de terminologie s'est introduit. Est-ce que quelqu'un le sait pour un fait?

Mais si tel est le cas, la fonction fmodf () de C (et probablement d'autres) sont très trompeuses. ils devraient être étiquetés fremf (), etc.

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

Pour les entiers, c'est simple. Fais juste

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

où je suppose que Nc'est positif et représentable dans le type de x. Votre compilateur préféré devrait pouvoir optimiser cela, de sorte qu'il se termine par une seule opération de mod dans l'assembleur.

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

La surcharge des opérateurs 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 le modèle 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 le nom, des types à virgule flottante.

Pour les entiers, vous pouvez définir un modèle de fonction C ++ qui renvoie toujours un 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 écrivez simplement à la mod(a, b)place de a%b.

Ici, le type Integerdoit être un type entier signé.

Si vous voulez le comportement mathématique courant où le signe du reste est le même que le signe du diviseur, alors vous pouvez faire par exemple

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 Integer, que c'est un type signé.

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

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

Vous pouvez convertir un dividende en non signé d'une manière telle que:

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, il 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 d'une seule arithmétique supplémentaire par opération (et pas de condition) lorsque vous travaillez avec un diviseur constant, elle est donc utilisable dans des applications de type DSP.

Il y a un cas particulier, où le diviseur est 2 ^N (puissance entière de deux), pour lequel le modulo peut être calculé en utilisant une arithmétique simple et une logique binaire comme

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 manière plus courante et moins délicate est d'obtenir 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;
}

Ce résultat est juste correct s'il est négatif.

Vous pouvez également tromper:

(p% q + q)% q

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

Je crois qu'une autre solution à ce problème serait d'utiliser des variables de type long au lieu de int.

Je travaillais juste sur un code où l'opérateur% renvoyait une valeur négative qui causait des problèmes (pour générer des variables aléatoires uniformes sur [0,1], vous ne voulez pas vraiment de nombres négatifs :)), mais après avoir changé les variables en tapez long, tout fonctionnait bien et les résultats correspondaient à ceux que j'obtenais en exécutant le même code en python (important pour moi car je voulais pouvoir générer les mêmes nombres «aléatoires» sur plusieurs plates-formes.

Voici une nouvelle réponse à une ancienne question, basée sur cet article de Microsoft Research et ses références.

Notez qu'à partir de C11 et C ++ 11, la sémantique de divest devenue une troncature vers zéro (voir [expr.mul]/4). De plus, pour Ddivisé par d, C ++ 11 garantit ce qui suit sur le quotient qTet le resterT

auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));

où signumcorrespond à -1, 0, +1, selon que son argument est <, ==,> que 0 (voir cette Q&R pour le code source).

Avec une division tronquée, le signe du reste est égal au signe du dividendeD , c'est-à-dire -1 % 8 == -1. C ++ 11 fournit également une std::divfonction qui renvoie une structure avec des membres quotet remselon une division tronquée.

Il y a d'autres définitions possibles, par exemple la division dite par étage peut être définie en termes de division tronquée intégrée

auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));

Avec la division au sol, le signe du reste est égal au signe du diviseurd . Dans des langues telles que Haskell et Oberon, il existe des opérateurs intégrés pour la division par étage. En C ++, vous devez écrire une fonction en utilisant les définitions ci-dessus.

Encore une autre façon est la division euclidienne , qui peut également être définie en termes de division tronquée intégrée

auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);

Avec la division euclidienne, le signe du reste est toujours positif .

Pour une solution qui n'utilise pas de branches et seulement 1 mod, vous pouvez faire ce qui suit

// Works for other sizes too,
// assuming you change 63 to the appropriate value
int64_t mod(int64_t x, int64_t div) {
  return (x % div) + (((x >> 63) ^ (div >> 63)) & div);
}

/ * Attention: le macro mod évalue plusieurs fois les effets secondaires de ses arguments. * /
#define mod (r, m) (((r)% (m)) + ((r) <0)? (m): 0)

... ou simplement vous habituer à trouver un représentant pour la classe d'équivalence.

Exemple de modèle pour C ++

template< class T >
T mod( T a, T b )
{
    T const r = a%b;
    return ((r!=0)&&((r^b)<0) ? r + b : r);
}

Avec ce modèle, le reste retourné sera nul ou aura le même signe que le diviseur (dénominateur) (l'équivalent de l'arrondi vers l'infini négatif), au lieu que le comportement C ++ du reste soit nul ou ayant le même signe que le dividende ( numérateur) (l'équivalent de l'arrondissement vers zéro).

define  MOD(a, b)       ((((a)%(b))+(b))%(b))

unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}

Cette solution (à utiliser quand modest positive) évite de prendre toutes ensemble des opérations de division négative ou de reste:

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}

Je ferais:

((-1)+8) % 8 

Ceci ajoute le dernier nombre au premier avant de faire le modulo donnant 7 comme souhaité. Cela devrait fonctionner pour n'importe quel nombre jusqu'à -8. Pour -9, ajoutez 2 * 8.