C의 Python 스타일 정수 나누기 및 모듈러스

StackOverflow https://stackoverflow.com/questions/828092

문제

Python과 Ruby에서 부호 있는 정수 나누기는 음의 무한대로 잘리고 부호 있는 정수 모듈러스는 두 번째 피연산자와 동일한 부호를 갖습니다.

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

그러나 C와 Java에서는 부호 있는 정수 나누기가 0 쪽으로 잘리고 부호 있는 정수 모듈러스는 첫 번째 피연산자와 동일한 부호를 갖습니다.

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

Python 및 Ruby에서와 동일한 종류의 분할 및 모듈러스를 C에서 수행하는 가장 간단하고 효율적인 방법은 무엇입니까?

도움이 되었습니까?

해결책

서명 된 정수 부서와 반올림 방향은 구형 C 표준에 지정되지 않습니다. 그러나 C99에서는 0으로 반올림하도록 지정됩니다.

다음은 C 표준 및 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;
}

나는 약간의 피상적 인 테스트를했고 파이썬과 동일한 결과를 제공하는 것으로 보입니다. 이 코드는 최대로 효율적이지 않을 수 있지만 우수한 C 컴파일러는 특히 헤더에 정적 함수로 코드를 넣는 경우 적절하게 최적화 할 수 있습니다.

이 밀접하게 관련된 질문을 살펴볼 수도 있습니다. C ++의 네거티브가있는 정수 디비전 반올림.

다른 팁

모듈로의 경우 다음이 가장 간단합니다.구현의 부호 규칙이 무엇인지는 중요하지 않습니다. 결과를 원하는 부호로 강제하면 됩니다.

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

분명히 그것은 긍정적인 a에 대한 것입니다.음수 a의 경우 다음이 필요합니다.

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

(아마 약간 혼란스러울 수도 있지만) 결합하여 다음을 제공합니다(C++에서.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;
}

a!=0을 이미 알고 있거나 %가 정의되지 않았기 때문에 cheapskate의 두 값을 갖는 "부호" 함수를 사용할 수 있습니다.

나눗셈에도 동일한 원리를 적용합니다(입력보다는 출력을 살펴보세요).

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

곱셈은 ​​필요한 것보다 비용이 더 많이 들 수 있지만 필요한 경우 나중에 아키텍처별로 미세하게 최적화할 수 있습니다.예를 들어, 몫과 나머지를 제공하는 나눗셈 연산이 있는 경우 나눗셈을 위해 정렬됩니다.

[편집하다:예를 들어 몫이나 나머지가 INT_MAX 또는 INT_MIN인 경우처럼 이것이 잘못된 경우가 있을 수 있습니다.그러나 큰 값에 대해 Python 수학을 에뮬레이트하는 것은 어쨌든 완전히 다른 질문입니다 ;-)]

[또 다른 편집:표준 Python 구현이 C로 작성되지 않았습니까?그들이 하는 일에 대한 소스를 트롤링할 수 있습니다.]

다음은 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 가지고 있기 때문에 사용됩니다 잘 정의 된 행동.

C ++ 11을 사용하는 경우 다음은 Floor Division 및 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);
}

C99 및 C ++ 11에서는 사용을 피할 수 있습니다. div C에서 분할 및 계수의 동작은 더 이상 구현에 의존하지 않기 때문입니다.

이 질문에 대한 해결책이 이미 제시된 것보다 훨씬 짧습니다 (코드). 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 중 하나에 대해이 솔루션을 벤치마킹 할 때이 솔루션이 절반 만 빠르게 수행한다는 것이 분명해집니다.

교훈은 : 분기 지침이 코드를 느리게 만드는 반면, 디비전 지침은 훨씬 더 나쁩니다!

그럼에도 불구하고 나는이 솔루션을 우아하게 만 게시한다고 생각했다.

이 질문은 파이썬 스타일의 정수 부서와 모듈로를 모방하는 방법에 대해 물었습니다. 여기에 주어진 모든 답변은이 작업의 피연산자가 정수 자체라고 가정하지만 Python은 모듈로 작동에 플로트를 사용할 수도 있습니다. 따라서 다음 답변은 문제를 더 잘 해결한다고 생각합니다.

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

그리고 모듈로를 위해 :

#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 Division 및 Modulo의 동작을 6320 개의 테스트 케이스에 제시 한 C 구현과 비교합니다. 비교가 성공하기 때문에 내 솔루션이 각 작업에 대한 Python의 동작을 올바르게 구현한다고 생각합니다.

그것은 못생긴 수레의 세계를 탐구하지만, 이것들은 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);
}

나는 그들의 효율성에 대한 주장을하지 않습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top