Целочисленное деление и модуль в стиле Python в C

Ответ 1

Направление округления со знаком целочисленного деления не указано в старых стандартах C. Тем не менее, в C99 указано округление до нуля.

Здесь переносимый код, который работает со всеми версиями стандартов C и архитектуры процессора:

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

Я сделал некоторые поверхностные тесты и, похоже, дал те же результаты, что и Python. Этот код может не быть максимально эффективным, но хороший компилятор C может, вероятно, оптимизировать его, особенно если вы введете код в заголовок как статические функции.

Вы также можете взглянуть на этот близкий вопрос: Целочисленное деление округления с негативами на С++.

Ответ 2

Для modulo я нахожу следующий простейший. Неважно, что означает соглашение об объявлении реализации, мы просто принуждаем результат к знаку, который нам нужен:

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

Очевидно, что для положительных a. Для отрицательного а вам нужно:

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

Что (возможно, немного смутно) объединяет, чтобы дать следующее (в С++. В C делать то же самое с int, а затем утомительно писать дубликат надолго):

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

Мы можем использовать двузначную функцию знака cheapskate, потому что мы уже знаем a!= 0, или% будет undefined.

Применяя тот же принцип к делению (посмотрите на выход, а не на вход):

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

Умножения, возможно, могут быть более дорогими, чем необходимо, но при необходимости могут быть оптимизированы с микроуровневой структурой на основе каждой архитектуры. Например, если у вас есть операция деления, которая дает вам коэффициент и остаток, то вы отсортированы для деления.

[Редактировать: могут быть некоторые случаи кросс, где это происходит не так, например, если частное или остальное - INT_MAX или INT_MIN. Но эмуляция математики python для больших значений - это еще один вопрос: -)]

[Другое редактирование: не стандартная реализация python, написанная на C? Вы можете тралить источник на то, что они делают]

Ответ 3

Вот простая реализация разделенного на пол и модуля в 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;
}

Здесь используется div, потому что он имеет корректное поведение.

Если вы используете С++ 11, это шаблонная реализация разделенного на пол и модуля:

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

В C99 и С++ 11 вы можете избежать использования div, поскольку поведение деления и модуля в C больше не зависит от реализации.

Ответ 4

Существует решение этого вопроса, которое намного короче (в коде), чем уже представленные. Я буду использовать формат ответа Ville Laurikari для моего:

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

К сожалению, похоже, что вышеупомянутые решения не работают хорошо. Когда сравнивая это решение с Ville Laurikari, становится очевидным, что это решение работает только наполовину быстрее.

Урок: В то время как инструкции ветвления делают код медленным, инструкции разделения намного хуже!

Я думал, что я все же отправляю это решение, если только для его элегантности.

Ответ 5

Вопрос о том, как эмулировать целочисленное деление и по модулю в стиле Python. Все приведенные здесь ответы предполагают, что операнды этой операции являются целыми числами, но Python также может использовать float для своей модульной операции. Таким образом, я думаю, что следующий ответ решает проблему еще лучше:

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

И для 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));
}

Я тестировал две вышеуказанные программы против того, как Python ведет себя с помощью следующего тестового кода:

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

Вышеприведенное будет сравнивать поведение деления Python и по модулю с C реализаций, которые я представил на 6320 тестовых площадках. Поскольку сравнение было успешным, Я считаю, что мое решение правильно реализует поведение Python соответствующие операции.

Ответ 6

Он проникает в уродливый мир плавающих, но они дают правильные ответы в 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);
}

Я не утверждаю об их эффективности.