Python stile intero divisione e modulo in C

Question

In Python e Ruby, la divisione intera firmato tronca verso l'infinito negativo, e firmato il modulo intero ha lo stesso segno del secondo operando:

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

Tuttavia, in C e Java , divisione intera firmato tronca verso 0, e firmato il modulo intero ha lo stesso segno come primo operando:

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

Qual è il modo più semplice ed efficace in C per eseguire lo stesso tipo di divisione e modulo come in Python e Ruby?

Answer 1

La direzione per l'arrotondamento con divisione intera con segno non è specificata negli standard C precedenti. Tuttavia, in C99 viene specificato il round verso zero.

Ecco il codice portatile che funziona con tutte le versioni degli standard C e architetture di 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; 
} 

Ho fatto alcuni test superficiali e sembra dare gli stessi risultati come Python. Questo codice potrebbe non essere al massimo efficiente, ma un buon compilatore C può probabilmente ottimizzarlo adeguatamente, specialmente se si inserisce il codice in un'intestazione come funzioni statiche.

Si consiglia inoltre di dare un'occhiata a questa domanda strettamente correlata: Integer division rounding with negatives in C++.

Answer 2

Si approfondisce il brutto mondo di carri, ma questi dare risposte corrette in 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); 
} 

Non faccio affermazioni circa la loro efficienza.

Answer 3

Per modulo, trovo il seguente più semplice. Non importa che cosa convenzione di segno del implementazione è, dobbiamo solo costringere il risultato al segno che vogliamo:

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

Ovviamente questo è positiva a. Per negativo una è necessario:

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

Che (forse un po 'confusamente) combina per fornire le seguenti (in C++ In C fare la stessa cosa con int, e quindi noiosamente scrivere un duplicato per lungo tempo.):

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

Possiamo usare una funzione "segno" a basso costo con due valori perché sappiamo già un! = 0, altrimenti% non sarà definito.

Applicando lo stesso principio di divisione (guardare in uscita anziché l'input):

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

Le moltiplicazioni forse potrebbero essere più costoso del necessario, ma può essere micro-ottimizzato seguito su un per-architettura base se necessario. Ad esempio se hai un op di divisione che ti dà quoziente e resto, allora sei ordinato per divisione.

[Modifica: potrebbero esserci alcuni casi limite in cui ciò non va, ad esempio se il quoziente o il resto è INT_MAX o INT_MIN.Ma emulare la matematica di Python per grandi valori è comunque un'altra questione ;-)]

[Un'altra modifica: non è l'implementazione standard di Python scritta in C? Si potrebbe traino la fonte per quello che fanno]

Answer 4

Ecco una semplice implementazione della divisione pavimenti e modulo in 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; 
} 

Qui, div viene utilizzato perché ha well-defined behavior.

Se stai usando C++ 11, ecco un implementazione su modelli di divisione pavimenti e modulo:

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

In C99 e C++ 11, è possibile evitare di utilizzare div in quanto il comportamento della divisione e il modulo in C non dipendono più dall'implementazione.

Answer 5

C'è una soluzione a questa domanda che è molto più breve (in codice) di quelli già presentati. Userò il formato della risposta di Ville Laurikari per la mia:

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

Purtroppo, sembra che le soluzioni di cui sopra non sono un buon rendimento. Quando si confronta questa soluzione con quella di Ville Laurikari, diventa evidente che questa soluzione ha prestazioni solo la metà della velocità.

La lezione è: mentre le istruzioni di ramificazione rendono il codice lento, le istruzioni di divisione sono molto peggiori!

Ho pensato tuttavia di pubblicare questa soluzione, se non altro per la sua eleganza.

Answer 6

La domanda è stata posta su come emulare la divisione integer e il modulo in stile Python. Tutte le risposte qui fornite presuppongono che gli operandi di questa operazione siano interi, ma Python può anche usare float per la sua operazione modulo. Quindi, penso che la seguente risposta risolve il problema ancora meglio:

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

E per il 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)); 
} 

ho testato i due programmi di cui sopra nei confronti di come Python si comporta utilizzando il seguente codice di prova:

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

Quanto sopra confronterà il comportamento della divisione e del modulo Python con le implementazioni C presentate in 6320 testicoli. Dal momento che il confronto è riuscito, credo che la mia soluzione implementa correttamente il comportamento di Python delle rispettive operazioni .