Division entière de type Python et module en C

La direction pour arrondir avec une division entière signée n’est pas spécifiée dans les normes C plus anciennes. Cependant, en C99, il est spécifié d’arrondir vers zéro.

Voici un code portable qui fonctionne avec toutes les versions des normes C et des architectures de processeur:

 int py_div(int a, int b) { if (a < 0) if (b < 0) return -a / -b; else return -(-a / b) - (-a % b != 0 ? 1 : 0); else if (b < 0) return -(a / -b) - (a % -b != 0 ? 1 : 0); else return a / b; } int py_mod(int a, int b) { if (a < 0) if (b < 0) return -(-a % -b); else return -a % b - (-a % -b != 0 ? 1 : 0); else if (b < 0) return -(a % -b) + (-a % -b != 0 ? 1 : 0); else return a % b; } 

J'ai fait des tests superficiels et cela semble donner les mêmes résultats que Python. Ce code n'est peut-être pas extrêmement efficace, mais un bon compilateur C peut probablement l'optimiser de manière adéquate, notamment si vous placez le code dans un en-tête sous forme de fonctions statiques.

Vous voudrez peut-être aussi jeter un coup d'œil à cette question étroitement liée: Arrondissement des divisions entières avec des négatifs en C ++ .

Pour modulo, je trouve le suivant le plus simple. Peu importe la convention de signe de l’implémentation, nous imposons simplement le résultat au signe que nous voulons:

 r = n % a; if (r < 0) r += a; 

Évidemment c'est positif a. Pour un négatif, vous avez besoin de:

 r = n % a; if (r > 0) r += a; 

Ce qui (peut-être un peu déroutant) se combine pour donner ce qui suit (en C ++. En C, faites la même chose avec int, puis écrivez fastidieusement une copie pendant longtemps):

 template T sign(T t) { return t > T(0) ? T(1) : T(-1); } template T py_mod(T n, T a) { T r = n % a; if (r * sign(a) < T(0)) r += a; return r; } 

Nous pouvons utiliser une fonction de "signe" à deux valeurs de cheapskate car nous connaissons déjà un! = 0, sinon le% serait indéfini.

Appliquer le même principe à la division (voir le résultat plutôt que l’entrée):

 q = n / a; // assuming round-toward-zero if ((q < 0) && (q * a != n)) --q; 

Les multiplications pourraient sans doute être plus coûteuses que nécessaire, mais peuvent être micro-optimisées ultérieurement sur une base par architecture si nécessaire. Par exemple, si vous avez une opération de division qui vous donne le quotient et le rest, alors vous êtes sortingés pour la division.

[Éditer: il peut y avoir des cas extrêmes où cela va mal, par exemple si le quotient ou le rest est INT_MAX ou INT_MIN. Mais émuler les maths python pour les grandes valeurs est une toute autre question ;-)]

[Une autre édition: l'implémentation standard de python n'est-elle pas écrite en C? Vous pouvez rechercher la source pour ce qu’ils font]

Voici une implémentation simple de la division et du module en C89:

 #include  div_t div_floor(int x, int y) { div_t r = div(x, y); if (r.rem && (x < 0) != (y < 0)) { r.quot -= 1; r.rem += y; } return r; } 

Ici, div est utilisé car il a un comportement bien défini .

Si vous utilisez C ++ 11, voici une implémentation basée sur un modèle de division et de module:

 #include  template std::tuple div_floor(Integral x, Integral y) { typedef std::tuple result_type; const Integral quot = x / y; const Integral rem = x % y; if (rem && (x < 0) != (y < 0)) return result_type(quot - 1, rem + y); return result_type(quot, rem); } 

En C99 et C ++ 11, vous pouvez éviter d'utiliser div car le comportement de division et de module dans C ne dépend plus de l'implémentation.

Il y a une solution à cette question beaucoup plus courte (en code) que celle déjà présentée. Je vais utiliser le format de la réponse de Ville Laurikari pour le mien:

 int py_div(int a, int b) { return (a - (((a % b) + b) % b)) / b); } int py_mod(int a, int b) { return ((a % b) + b) % b; } 

Malheureusement, il semble que les solutions ci-dessus ne fonctionnent pas bien. En comparant cette solution à celle de Ville Laurikari, il devient évident que cette solution est deux fois moins rapide.

La leçon est la suivante: pendant que les instructions de twigment ralentissent le code, les instructions de division sont bien pires!

Je pensais néanmoins poster cette solution, ne serait-ce que pour son élégance.

La question était de savoir comment émuler la division entière et le modulo de style Python. Toutes les réponses données ici supposent que les opérandes de cette opération sont eux-mêmes des entiers, mais Python peut également utiliser des flottants pour son opération modulo. Ainsi, je pense que la réponse suivante résout le problème encore mieux:

 #include  #include  #include  int pydiv(double a, double b) { int q = a/b; double r = fmod(a,b); if ((r != 0) && ((r < 0) != (b < 0))) { q -= 1; } return q; } int main(int argc, char* argv[]) { double a = atof(argv[1]); double b = atof(argv[2]); printf("%d\n", pydiv(a, b)); } 

Et pour le modulo:

 #include  #include  #include  double pymod(double a, double b) { double r = fmod(a, b); if (r!=0 && ((r<0) != (b<0))) { r += b; } return r; } int main(int argc, char* argv[]) { double a = atof(argv[1]); double b = atof(argv[2]); printf("%f\n", pymod(a, b)); } 

J'ai testé les deux programmes ci-dessus en fonction du comportement de Python en utilisant le code de test suivant:

 #!/usr/bin/python3 import subprocess subprocess.call(["cc", "pydiv.c", "-lm", "-o", "cdiv"]) subprocess.call(["cc", "pymod.c", "-lm", "-o", "cmod"]) def frange(start, stop, step=1): for i in range(0, int((stop-start)/step)): yield start + step*i for a in frange(-10.0, 10.0, 0.25): for b in frange(-10.0, 10.0, 0.25): if (b == 0.0): continue pydiv = a//b pymod = a%b cdiv = int(subprocess.check_output(["./cdiv", str(a), str(b)])) cmod = float(subprocess.check_output(["./cmod", str(a), str(b)])) if pydiv != cdiv: exit(1) if pymod != cmod: exit(1) 

Ce qui précède comparera le comportement de la division Python et du modulo avec les implémentations C que j'ai présentées sur 6320 cas de test. Depuis que la comparaison a réussi, je pense que ma solution implémente correctement le comportement des opérations respectives de Python.

Il plonge dans le monde laid des flotteurs, mais ceux-ci donnent des réponses correctes en Java:

 public static int pythonDiv(int a, int b) { if (!((a < 0) ^ (b < 0))) { return a / b; } return (int)(Math.floor((double)a/(double)b)); } public static int pythonMod(int a, int b) { return a - b * pythonDiv(a,b); } 

Je ne fais aucune affirmation sur leur efficacité.