División de enteros estilo Python & amp; módulo en C

Question

En Python y Ruby, la división de enteros con signo se trunca hacia el infinito negativo, y el módulo de enteros con signo tiene el mismo signo que el segundo operando:

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

Sin embargo, en C y Java, la división de enteros con signo se trunca hacia 0, y el módulo de enteros con signo tiene el mismo signo que el primer operando:

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

¿Cuál es la forma más simple y eficiente en C para realizar el mismo tipo de división y módulo que en Python y Ruby?

Answer 1

La dirección para el redondeo con división de enteros con signo no se especifica en los estándares C anteriores. Sin embargo, en C99 se especifica para redondear hacia cero.

Aquí hay un código portátil que funciona con todas las versiones de los estándares C y las arquitecturas 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;
}

Hice algunas pruebas superficiales y parece dar los mismos resultados que Python. Es posible que este código no sea lo más eficiente posible, pero un buen compilador de C probablemente pueda optimizarlo adecuadamente, especialmente si coloca el código en un encabezado como funciones estáticas.

También puede querer echar un vistazo a esta pregunta estrechamente relacionada: Integer redondeo de división con negativos en C ++ .

Answer 2

Para módulo, encuentro lo siguiente más simple. No importa cuál sea la convención de signos de la implementación, simplemente forzamos el resultado al signo que queremos:

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

Obviamente eso es positivo a. Para una negativa necesitas:

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

Que (quizás un poco confuso) se combina para dar lo siguiente (en C ++. En C, haga lo mismo con int, y luego escriba tediosamente un duplicado por mucho tiempo):

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

Podemos usar un signo de tacaño de dos valores " funcionar porque ya sabemos a! = 0, o el% no estaría definido.

Aplicar el mismo principio a la división (observe la salida en lugar de la entrada):

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

Podría decirse que las multiplicaciones podrían ser más caras de lo necesario, pero pueden ser micro-optimizadas más adelante según la arquitectura si es necesario. Por ejemplo, si tiene una operación de división que le da cociente y resto, entonces está ordenado por división.

[Editar: puede haber algunos casos extremos donde esto sale mal, por ejemplo si el cociente o el resto es INT_MAX o INT_MIN. Pero emular las matemáticas de Python para valores grandes es una pregunta completamente diferente ;-)]

[Otra edición: ¿no está la implementación estándar de Python escrita en C? Podría rastrear la fuente de lo que hacen]

Answer 3

Aquí hay una implementación simple de división en pisos y módulo 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;
}

Aquí, div se usa porque tiene comportamiento bien definido .

Si está utilizando C ++ 11, aquí hay una implementación de plantilla de división y módulo de piso:

#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 y C ++ 11, puedes evitar usar div porque el comportamiento de la división y el módulo en C ya no depende de la implementación.

Answer 4

Hay una solución a esta pregunta que es mucho más corta (en código) que las ya presentadas. Usaré el formato de la respuesta de Ville Laurikari para la mía:

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

Lamentablemente, parece que las soluciones anteriores no están funcionando bien. Al comparar esta solución con la de Ville Laurikari, se hace evidente que esta solución funciona solo la mitad de rápido.

La lección es: ¡mientras que las instrucciones de bifurcación hacen que el código sea lento, las instrucciones de división son mucho peores!

Sin embargo, pensé que publicaría esta solución aunque solo fuera por su elegancia.

Answer 5

La pregunta formulada sobre cómo emular la división y el módulo de enteros al estilo de Python. Todas las respuestas dadas aquí asumen que los operandos de esta operación son enteros, pero Python también puede usar flotantes para su operación de módulo. Por lo tanto, creo que la siguiente respuesta resuelve el problema aún mejor:

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

Y para el 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));
}

Probé los dos programas anteriores contra el comportamiento de Python usando el siguiente código de prueba:

#!/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)

Lo anterior comparará el comportamiento de la división y el módulo de Python con la C Implementaciones que presenté en 6320 testcases. Dado que la comparación tuvo éxito, Creo que mi solución implementa correctamente el comportamiento de Python de respectivas operaciones.

Answer 6

Se adentra en el feo mundo de los flotadores, pero estos dan respuestas correctas 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);
}

No hago afirmaciones sobre su eficiencia.