Python-style ganzzahlige Teilung und Modul in C

Question

In Python und Ruby unterzeichnete ganzzahlige Division abschneidet Richtung negativ unendlich und Ganzzahl mit Vorzeichen Modul dem gleichen Vorzeichen des zweiten Operanden:

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

jedoch in C und Java, signiert ganzzahlige Division abschneidet gegen 0, und Ganzzahl mit Vorzeichen Modul das gleiche Vorzeichen wie der erste Operand:

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

Was ist die einfachste und effizienteste Art und Weise in C die gleiche Art von Teilung und Modul wie in Python und Ruby?

auszuführen

Answer 1

Die Richtung mit signierter Integer-Division zum Runden ist nicht in älteren C-Normen festgelegt. Doch in C99 wird festgelegt, in Richtung Null runden.

Hier portablen Code, die mit allen Versionen der C-Normen und CPU-Architekturen funktionieren:

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 und es scheint, die gleichen Ergebnisse wie Python zu geben. Dieser Code kann nicht maximal effizient sein, aber ein guter C-Compiler kann es wahrscheinlich angemessen optimieren, vor allem, wenn Sie den Code in einem Header als statische Funktionen setzen.

Sie können auch einen Blick auf diese eng verwandte Frage nehmen: Integer Division mit Negativen in C ++ gerundet wird.

Answer 2

Für Modulo, finde ich die folgende einfachsten. Es spielt keine Rolle, was die Vorzeichenkonvention der Umsetzung ist, zwingen wir nur das Ergebnis an das Zeichen, das wir wollen:

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

Ganz offensichtlich ist das für positiv ein. Für negative a benötigen Sie:

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

Welche (vielleicht ein wenig verwirrend) kombiniert die folgenden geben (in C ++ In C die gleiche Sache mit int tun, und dann mühsam ein Duplikat für lange lange 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 knauserig zweiwertig „Zeichen“ Funktion verwenden, da wir bereits einen wissen! = 0 oder% würden nicht definiert werden.

Die Anwendung des gleichen Prinzip der Teilung (Blick auf die Ausgabe anstatt der Eingabe):

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

Die Multiplikationen wohl könnte teurer sein als notwendig, kann aber Mikro-optimierte später auf einer Pro-Architektur Basis sein, wenn es sein muss. Wenn Sie zum Beispiel eine Abteilung op haben, die Ihnen Quotienten und den Rest gibt, dann sind Sie für die Teilung sortieren.

[Edit: es könnte einige Ränder Fälle, in denen dies schief geht, zum Beispiel, wenn der Quotient oder der Rest INT_MAX oder INT_MIN ist. Aber Mathematik für große Werte Python Emulation ist eine ganz andere Frage sowieso; -)]

[Ein weiterer edit: ist nicht die Standard-Python-Implementierung in C geschrieben? Sie könnten die Quelle Schleppnetz für das, was sie tun]

Answer 3

Hier ist eine einfache Implementierung von Böden Teilung und des Moduls 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 verwendet, weil es wohldefinierte Verhalten .

Wenn Sie mit C ++ 11, hier ist eine Templat Implementierung von Boden Division und Modul:

#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 mit div da das Verhalten der Teilung und des Moduls in C sind nicht mehr auf die Umsetzung abhängen vermeiden.

Answer 4

Es gibt eine Lösung für diese Frage, die viel kürzer (in Code) als die bereits Beschenkten ist. Ich werde das Format von Ville Laurikari Antwort für Mine 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 scheint es, dass die oben genannten Lösungen nicht gut durchführen. Wenn Benchmarking diese Lösung gegen die eine von Ville Laurikari, wird deutlich, dass diese Lösung so schnell nur die Hälfte führt.

Die Lektion ist: Während Verzweigungsanweisungen, Code langsam machen Divisionsbefehle sind viel schlimmer

!

Ich dachte, ich doch diese Lösung abgeben nur für seine Eleganz.

Answer 5

Die Frage, wie Python-Stil Integer-Division und Modulo zu emulieren. Alle hier gegebenen Antworten übernehmen die Operanden dieser Operation ganzen Zahlen selbst zu sein, aber Python kann auch Schwimmer für seine Modulo-Operation verwenden. So denke ich, die folgende Antwort löst das Problem noch besser:

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

Für die 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));
}

Ich testete die beiden oben genannten Programme gegen wie Python verhält sich die folgenden Testcode:

#!/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 oben wird das Verhalten von Python Division vergleichen und Modulo mit dem C Implementierungen I auf 6320 Testfälle dargestellt. Da der Vergleich erfolgreich war, Ich glaube, dass meine Lösung korrekt implementiert Python das Verhalten der jeweilige Operationen.

Answer 6

Es vertieft sich in die hässliche Welt der Schwimmer, aber diese geben die richtigen Antworten 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);
}

Ich mache keine Aussagen über ihre Effizienz.