Division et modulus d'entiers à la Python en C

Question

En Python et Ruby, la division des entiers signés est tronquée vers l'infini négatif, et le modulus des entiers signés a le même signe que le second opérande :

>>> (-41) / 3
-14
>>> (-41) % 3
1

Cependant, en C et en Java, la division des entiers signés est tronquée vers 0, et le modulus des entiers signés a le même signe que le premier opérande :

printf("%d\n", (-41) / 3); /* prints "-13" */
printf("%d\n", (-41) % 3); /* prints "-2" */

Quelle est la méthode la plus simple et la plus efficace en C pour effectuer le même type de division et de modulus qu'en Python et Ruby ?

Answer 1

Le sens de l'arrondi avec la division d'entiers signés n'est pas spécifié dans les anciennes normes C. Cependant, en C99, il est spécifié d'arrondir vers zéro.

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

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 quelques tests superficiels et il semble donner les mêmes résultats que Python. Ce code n'est peut-être pas d'une efficacité maximale, mais un bon compilateur C peut probablement l'optimiser de manière adéquate, surtout si vous placez le code dans un en-tête en tant que fonctions statiques.

Vous pouvez également jeter un coup d'œil à cette question étroitement liée : Arrondissement de la division des nombres entiers avec les négatifs en C++ .

Answer 2

Pour le modulo, je trouve que la méthode suivante est la plus simple. La convention de signe de l'implémentation n'a pas d'importance, il suffit de contraindre le résultat au signe que nous voulons :

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

Évidemment, c'est pour un a positif. Pour un a négatif, il faut.. :

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

Ce qui (peut-être un peu confusément) se combine pour donner ce qui suit (en C++. En C, faites la même chose avec int, puis écrivez fastidieusement un duplicata pour long long) :

template<typename T> T sign(T t) { return t > T(0) ? T(1) : T(-1); }

template<typename T> 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 "signe" à deux valeurs, car nous savons déjà que a!=0, sinon le % serait indéfini.

Appliquer le même principe à la division (regarder la sortie 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 elles 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 reste, alors vous êtes trié pour la division.

[Edit : il peut y avoir des cas limites où cela se passe mal, par exemple si le quotient ou le reste est INT_MAX ou INT_MIN. Mais émuler les maths de Python pour les grandes valeurs est une toute autre question de toute façon ;-)].

[Autre modification : l'implémentation standard de Python n'est-elle pas écrite en C ? Vous pourriez parcourir les sources pour savoir ce qu'ils font].

Answer 3

Il existe une solution à cette question qui est beaucoup plus courte (en code) que celles déjà présentées. Je vais utiliser le format de la réponse de Ville Laurikari pour la mienne :

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 donnent pas de bons résultats. En comparant cette solution à celle de Ville Laurikari, il apparaît que cette solution est deux fois moins rapide.

La leçon est la suivante : si les instructions de branchement rendent le code lent, les instructions de division sont bien pires !

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

Answer 4

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

#include <stdlib.h>

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é parce qu'il a un comportement bien défini .

Si vous utilisez C++11, voici une implémentation modélisée de la division et du modulus :

#include <tuple>

template<class Integral>
std::tuple<Integral, Integral> div_floor(Integral x, Integral y)
{
    typedef std::tuple<Integral, Integral> 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 l'utilisation de div puisque le comportement de la division et du module en C ne dépend plus de l'implémentation.

Answer 5

La question portait sur la manière d'émuler la division et la modulation d'entiers à la 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. Je pense donc que la réponse suivante résout encore mieux le problème :

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

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 <stdlib.h>
#include <stdio.h>
#include <math.h>

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 par rapport au 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 permet de comparer le comportement de la division et du modulo Python avec celui du C que j'ai présentées sur 6320 scénarios de test. Puisque la comparaison a réussi, je pense que ma solution implémente correctement le comportement de Python pour les opérations respectives.