Division entière de style Python & amp; module en C

Question

En Python et Ruby, la division entière signée tronque vers l'infini négatif et le module entier signé a le même signe que le deuxième 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 module 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" */

Quel est le moyen le plus simple et le plus efficace en C d’effectuer le même type de division et de module que celui en Python et en Ruby?

Answer 1

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é de arrondir à zéro.

Voici un code portable qui fonctionne avec toutes les versions des normes C et des 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 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 pouvez également consulter cette question étroitement liée: Integer arrondir les divisions avec les négatifs en C ++ .

Answer 2

Pour modulo, je trouve ce qui suit 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. 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<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 un "signe" à deux valeurs pour un radeau de skate, fonction parce que nous connaissons déjà un! = 0, sinon le% serait indéfini.

Appliquer le même principe à la division (regardez la sortie plutôt que l'entrée):

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

On pourrait soutenir que les multiplications pourraient être plus onéreuses que nécessaire, mais elles pourraient être optimisées ultérieurement, micro-optimisées 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és par division.

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

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

Answer 3

Voici une implémentation simple de la division et du module 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é car il présente 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 au sol:

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

Sous C99 et C ++ 11, vous pouvez éviter d'utiliser div car le comportement de la division et du module en C ne dépendent plus de l'implémentation.

Answer 4

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 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 ne fonctionne que deux fois moins vite.

La leçon est la suivante: alors que les instructions de branchement 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.

Answer 5

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 <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 à l'aide du 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 le C implémentations que j'ai présentées sur 6320 cas de test. Depuis que la comparaison a réussi, Je crois que ma solution implémente correctement le comportement de Python du opérations respectives.

Answer 6

Il plonge dans le vilain monde 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é.