Ganzzahldivision und -modul im Python-Stil in C

In Python und Ruby schneidet die Division ganzer Zahlen mit Vorzeichen in Richtung negativer Unendlichkeit ab, und der vorzeichenbehaftete Ganzzahlmodul hat das gleiche Vorzeichen wie der zweite Operand:

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

In C und Java schneidet die Division einer ganzen Zahl mit Vorzeichen jedoch in Richtung 0 ab, und der vorzeichenbehaftete Ganzzahlmodul hat das gleiche Vorzeichen wie der erste Operand:

printf("%dn", (-41) / 3); /* prints "-13" */
printf("%dn", (-41) % 3); /* prints "-2" */

Was ist der einfachste und effizienteste Weg in C, um dieselbe Art von Division und Modulus wie in Python und Ruby durchzuführen?

Die Rundungsrichtung bei vorzeichenbehafteter Integer-Division ist in älteren C-Standards nicht angegeben. In C99 ist jedoch angegeben, auf Null zu runden.

Hier ist tragbarer Code, der mit allen Versionen der C-Standards und CPU-Architekturen funktioniert:

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

Ich habe einige oberflächliche Tests durchgeführt und es scheint die gleichen Ergebnisse wie Python zu liefern. Dieser Code ist möglicherweise nicht maximal effizient, aber ein guter C-Compiler kann ihn wahrscheinlich angemessen optimieren, insbesondere wenn Sie den Code als statische Funktionen in einen Header einfügen.

Vielleicht möchten Sie auch einen Blick auf diese eng verwandte Frage werfen: Runden ganzer Divisionen mit negativen Werten in C++.

Für Modulo finde ich folgendes am einfachsten. Es spielt keine Rolle, wie die Vorzeichenkonvention der Implementierung lautet, wir zwingen das Ergebnis einfach in das gewünschte Vorzeichen:

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

Offensichtlich ist das positiv a. Für negative a brauchst du:

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

Was (vielleicht ein wenig verwirrend) kombiniert, um Folgendes zu ergeben (in C++. In C dasselbe mit int und dann mühsam lange ein Duplikat schreiben):

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

Wir können eine billige zweiwertige “Zeichen”-Funktion verwenden, da wir bereits a!=0 kennen, sonst wäre % undefiniert.

Wenden Sie das gleiche Prinzip auf die Division an (betrachten Sie die Ausgabe und nicht die Eingabe):

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

Die Multiplikationen könnten wohl teurer als nötig sein, können aber später bei Bedarf pro Architektur mikrooptimiert werden. Wenn Sie beispielsweise eine Divisionsoperation haben, die Quotienten und Rest ergibt, werden Sie nach Division sortiert.

[Edit: there might be some edge cases where this goes wrong, for instance if the quotient or the remainder is INT_MAX or INT_MIN. But emulating python maths for large values is a whole other question anyway ;-)]

[Another edit: isn’t the standard python implementation written in C? You could trawl the source for what they do]

Es gibt eine Lösung für diese Frage, die (im Code) viel kürzer ist als die bereits vorgestellten. Ich werde das Format von Ville Laurikaris Antwort für meine verwenden:

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

Leider scheinen die oben genannten Lösungen nicht gut zu funktionieren. Beim Benchmarking dieser Lösung mit der von Ville Laurikari fällt auf, dass diese Lösung nur halb so schnell arbeitet.

Die Lektion ist: Während Verzweigungsbefehle den Code verlangsamen, sind Divisionsbefehle viel schlimmer!

Ich dachte, ich poste diese Lösung dennoch, wenn auch nur wegen ihrer Eleganz.

Hier ist eine einfache Implementierung von Etagenteilung und Modul 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;
}

Hier, div wird verwendet, weil es ein wohldefiniertes Verhalten hat.

Wenn Sie C++11 verwenden, sehen Sie hier eine Schablonenimplementierung von Floored Division und Modulus:

#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 und C++11 können Sie die Verwendung von . vermeiden div da das Verhalten von Division und Modul in C nicht mehr von der Implementierung abhängen.

Die Frage stellte sich, wie man Ganzzahldivision und Modulo im Python-Stil emuliert. Alle hier gegebenen Antworten gehen davon aus, dass die Operanden dieser Operation selbst Ganzzahlen sind, aber Python kann auch Gleitkommazahlen für seine Modulo-Operation verwenden. Daher denke ich, dass die folgende Antwort das Problem noch besser löst:

#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("%dn", pydiv(a, b));
}

Und für das 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("%fn", pymod(a, b));
}

Ich habe die beiden oben genannten Programme anhand des folgenden Testcodes anhand des Verhaltens von Python getestet:

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

Das Obige vergleicht das Verhalten von Python Division und Modulo mit den C-Implementierungen, die ich in 6320 Testfällen vorgestellt habe. Da der Vergleich gelungen ist, glaube ich, dass meine Lösung Pythons Verhalten der jeweiligen Operationen korrekt implementiert.

Es taucht in die hässliche Welt der Schwimmer ein, aber diese geben in Java die richtigen Antworten:

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

Ich mache keine Aussagen über ihre Effizienz.