de estilo Python división de enteros y módulo en C

Question

En Python y Ruby, división entero con signo trunca hacia el infinito negativo, y firmado módulo entero tiene el mismo signo el segundo operando:

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

Sin embargo, en C y Java , división de entero con signo trunca hacia 0, y firmado el módulo entero 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 manera más simple y más eficiente en C para realizar el mismo tipo de división y módulo como en Pitón y Ruby?

Answer 1

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

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

Es posible que desee echar un vistazo a esta pregunta estrechamente relacionada: Integer division rounding with negatives in C++.

Answer 2

Se profundiza en el mundo feo de flotadores, pero éstos 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 eficacia.

Answer 3

Para el módulo, encuentro lo siguiente más simple. No importa qué convención de signos de la aplicación es, acabamos de coaccionar el resultado a la señal que queremos:

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

Obviamente eso es positivo a. Para negativo una que necesita:

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

Qué (quizás un poco confusa) se combina para dar la siguiente (en C++ En C hacer lo mismo con int, y luego tediosamente escribir un duplicado de largo 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 utilizar un tacaño dos valorado la función "señal", porque ya sabemos! = 0, o el% estaríamos sin definir.

Aplicando el mismo principio a la división (se ven en la salida en lugar de la entrada):

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

las multiplicaciones posiblemente podrían ser más caros de lo necesario, pero puede ser micro-optimizado más tarde en un per-arquitectura base si es necesario. Por ejemplo, si tienes una operación de división que te da el cociente y el resto, entonces estás ordenado para la división.

[Editar: puede haber algunos casos extremos donde esto va 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 es la implementación estándar de Python escrita en C? Se podría arrastre a la fuente por lo que hacen]

Answer 4

Aquí es una sencilla aplicación de la división de plantas y el módulo de 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 utiliza porque tiene well-defined behavior.

Si estás usando C++ 11, aquí es una aplicación con plantilla de la división de plantas y módulo:

#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, se puede evitar el uso de div ya que el comportamiento de la división y el módulo en C ya no dependen de la implementación.

Answer 5

Hay una solución a esta pregunta que es mucho más corta (en código) que las ya presentadas. Voy a utilizar el formato de la respuesta de Ville Laurikari por 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; 
} 

Desafortunadamente, parece que las soluciones anteriores no están funcionando bien. Cuando se compara esta solución con la de Ville Laurikari, resulta 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!

Pensé que, sin embargo, publicaría esta solución solo por su elegancia.

Answer 6

La pregunta sobre cómo emular la división de enteros al estilo de Python y el módulo. Todas las respuestas dadas aquí suponen 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 módulo:

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

He probado los dos programas anteriores en contra de la forma en Python se comporta con 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 las implementaciones C que presenté en 6320 testcases. Dado que la comparación tuvo éxito, creo que mi solución implementa correctamente el comportamiento de Python de las operaciones respectivas de .