Divisione intera in stile Python & amp; modulo in C.

Question

In Python e Ruby, la divisione di numeri interi con segno si tronca verso l'infinito negativo e il modulo di numeri interi con segno ha lo stesso segno del secondo operando:

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

Tuttavia, in C e Java, la divisione di numeri interi con segno tronca verso 0 e il modulo di numeri interi con segno ha lo stesso segno del primo operando:

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

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

Answer 1

La direzione per l'arrotondamento con divisione intera con segno non è specificata negli standard C precedenti. Tuttavia, in C99 si specifica di arrotondare verso zero.

Ecco il codice portatile che funziona con tutte le versioni degli standard C e architetture della 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 di Python. Questo codice potrebbe non essere al massimo efficiente, ma un buon compilatore C può probabilmente ottimizzarlo adeguatamente, specialmente se lo inserisci in un'intestazione come funzioni statiche.

Potresti anche dare un'occhiata a questa domanda strettamente correlata: Integer arrotondamento delle divisioni con negativi in ??C ++ .

Answer 2

Per modulo, trovo quanto segue più semplice. Non importa quale sia la convenzione sui segni di implementazione, dobbiamo solo forzare il risultato sul segno che vogliamo:

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

Ovviamente è positivo per a. Per negativo a è necessario:

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

Che (forse un po 'confusamente) si combina per dare quanto segue (in C ++. In C fai la stessa cosa con int, e poi scrivi noiosamente un duplicato per molto 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 un cheapskate a due valori & sign; sign " funzione perché conosciamo già a! = 0 o% non sarebbe definito.

Applicazione dello stesso principio alla divisione (guarda l'output anziché l'input):

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

Probabilmente le moltiplicazioni potrebbero essere più costose del necessario, ma possono essere micro-ottimizzate successivamente in base all'architettura, se necessario. Ad esempio, se si dispone di un'operazione di divisione che fornisce quoziente e resto, allora si è ordinati per divisione.

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

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

Answer 3

Ecco una semplice implementazione della divisione e del modulo floored 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 comportamento ben definito .

Se si utilizza C ++ 11, ecco un'implementazione basata su modelli di divisione e modulo floored:

#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, puoi evitare di usare div poiché il comportamento della divisione e del modulo in C non dipendono più dall'implementazione.

Answer 4

C'è una soluzione a questa domanda che è molto più breve (nel 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;
}

Sfortunatamente, sembra che le soluzioni sopra non funzionino bene. Quando si confronta questa soluzione con quella di Ville Laurikari, diventa evidente che questa soluzione offre solo la metà della velocità.

La lezione è: mentre le istruzioni di diramazione rallentano il codice, le istruzioni di divisione sono molto peggio!

Pensavo di pubblicare questa soluzione, anche se solo per la sua eleganza.

Answer 5

La domanda su come emulare la divisione intera e il modulo in stile Python. Tutte le risposte fornite qui presuppongono che gli operandi di questa operazione siano numeri interi ma Python può anche usare i float per la sua operazione modulo. Pertanto, penso che la seguente risposta risolva 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 precedenti con il comportamento di Python usando il seguente codice di test:

#!/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 la C implementazioni che ho presentato su 6320 testcase. Poiché il confronto è riuscito, Credo che la mia soluzione attui correttamente il comportamento di Python rispettive operazioni.

Answer 6

Scava nel brutto mondo dei float, ma questi danno 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 sulla loro efficienza.