divisão inteira Python-estilo & módulo em C

Question

Em Python e Ruby, assinado inteiro trunca divisão para infinito negativo, e assinado inteiro módulo tem o mesmo sinal o segundo operando:

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

No entanto, em C e Java, assinado trunca divisão inteira na direção de 0, e assinado inteiro módulo tem o mesmo sinal que o primeiro operando:

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

O que é a maneira mais simples e mais eficiente em C para executar o mesmo tipo de divisão e módulo como em Python e Ruby?

Answer 1

A direção de arredondamento com divisão inteiro assinado não é especificado no padrão C mais velhos. No entanto, em C99 é especificado para arredondar para zero.

Aqui está o código portátil que funciona com todas as versões dos padrões C e arquiteturas de 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;
}

Eu fiz alguns testes superficiais e parece dar os mesmos resultados que Python. Este código pode não ser maximamente eficiente, mas um compilador bom C provavelmente pode otimizá-lo de forma adequada, especialmente se você colocar o código em um cabeçalho como funções estáticas.

Você também pode querer dar uma olhada nesta questão intimamente relacionados: Integer divisão de arredondamento com negativos em C ++ .

Answer 2

Para módulo, acho mais simples o seguinte. Não importa o que convenção de sinais da implementação é, nós apenas coagir o resultado para o sinal que queremos:

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

Obviamente que é para um positivo. Para um negativo que você precisa:

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

O que (talvez um pouco confusa) se combina para dar a seguinte (. Em C ++ Em C fazer a mesma coisa com o int e, em seguida, tediosamente escrever uma duplicata por muito tempo longo):

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

Podemos usar um pão-duro função de "sinal" dois valores porque nós já sabemos! = 0, ou a% seria indefinida.

Aplicando o mesmo princípio à divisão (olhar para a saída em vez da entrada):

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

As multiplicações sem dúvida poderia ser mais caro do que o necessário, mas pode ser micro-otimizado depois em uma base per-arquitetura se for necessário. Por exemplo, se você tem uma op divisão que lhe dá quociente e o resto, então você está classificado para a divisão.

[Editar: pode haver alguns casos extremos onde isso der errado, por exemplo, se o quociente ou o resto é INT_MAX ou INT_MIN. Mas emulando matemática Python para grandes valores é toda uma outra questão de qualquer maneira; -)]

[Outro edit: não é a implementação padrão do Python escrito em C? Você poderia arrasto a fonte para o que eles fazem]

Answer 3

Aqui está uma implementação simples da divisão de piso e módulo no 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;
}

Aqui, div é usado porque tem bem definida comportamento .

Se você estiver usando C ++ 11, aqui é uma implementação templated da divisão de piso e módulo:

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

Em C99 e C ++ 11, você pode evitar o uso div vez que o comportamento da divisão e módulo em C não são mais dependem da implementação.

Answer 4

Há uma solução para esta questão que é muito mais curto (em código) do que os já apresentados. Vou usar o formato da resposta de Ville Laurikari para meu:

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

Infelizmente, parece que as soluções acima não são um bom desempenho. Quando aferição esta solução com a de Ville Laurikari, torna-se evidente que esta solução executa apenas metade tão rápido.

A lição é: Enquanto instruções de desvio tornar o código lento, instruções de divisão são muito piores

Eu pensei que, no entanto, postar esta solução se apenas por sua elegância.

Answer 5

A pergunta sobre como emular divisão inteira Python-estilo e modulo. Todas as respostas dadas aqui assumir os operandos desta operação para serem eles mesmos números inteiros, mas Python também pode usar carros alegóricos para a sua operação de módulo. Assim, acho que os seguintes resolve responder ao problema ainda melhor:

#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 para o módulo:

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

Eu testei o acima de dois programas contra a forma como se comporta Python usando o seguinte código de teste:

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

O código acima irá comparar o comportamento da divisão de Python e modulo com o C implementações I apresentado em 6320 testcases. Desde a comparação sucedido, Acredito que a minha solução implementa corretamente o comportamento do Python respectivas operações.

Answer 6

Ele mergulha no mundo feio de carros alegóricos, mas estes dão respostas corretas em 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);
}

Não faço afirmações sobre a sua eficiência.