C / C ++에서 양수 모듈로를 얻는 가장 빠른 방법

C / C ++에서 양수 모듈로를 얻는 가장 빠른 방법

---

종종 내부 루프에서 "랩 어라운드"방식으로 배열을 인덱싱해야하므로 배열 크기가 100이고 코드에서 요소 -2를 요청하면 요소 98이 주어져야합니다. 파이썬처럼 간단하게를 사용할 수 my_array[index % array_size]있지만 어떤 이유로 C의 정수 산술 (보통)은 일관되게 반올림하는 대신 0으로 반올림하고 결과적으로 모듈로 연산자는 음의 첫 번째 인수가 주어지면 음의 결과를 반환합니다.

종종 나는 그것이 index보다 작지 않을 것이라는 것을 알고 -array_size있으며,이 경우 나는 단지 그렇게한다 my_array[(index + array_size) % array_size]. 그러나 때로는 이것이 보장 될 수 없으며 이러한 경우 항상 양성 모듈로 함수를 구현하는 가장 빠른 방법을 알고 싶습니다. 다음과 같이 분기없이 수행 할 수있는 몇 가지 "영리한"방법이 있습니다.

inline int positive_modulo(int i, int n) {
    return (n + (i % n)) % n
}

또는

inline int positive_modulo(int i, int n) {
    return (i % n) + (n * (i < 0))
}

물론 이것들을 프로파일 링하여 내 시스템에서 가장 빠른 것이 무엇인지 알아낼 수 있지만, 더 나은 것을 놓쳤거나 내 시스템에서 빠른 것이 다른 시스템에서 느릴 수 있다는 것에 대해 걱정할 수 없습니다.

이 작업을 수행하는 표준 방법이 있습니까, 아니면 가능한 가장 빠른 방법이 될 수있는 제가 놓친 영리한 트릭이 있습니까?

또한 나는 그것이 아마도 희망적인 생각이라는 것을 알고 있지만, 자동 벡터화 할 수있는 방법이 있다면 그것은 놀랍습니다.

---

대부분의 경우 컴파일러는 코드를 최적화하는 데 매우 능숙하므로 일반적으로 코드를 읽을 수있는 상태로 유지하는 것이 가장 좋습니다 (컴파일러와 다른 개발자가 수행중인 작업을 알 수 있도록).

배열 크기는 항상 양수이므로 몫을로 정의하는 것이 좋습니다 unsigned. 컴파일러는 작은 if / else 블록을 분기가없는 조건부 명령어로 최적화합니다.

unsigned modulo( int value, unsigned m) {
    int mod = value % (int)m;
    if (value < 0) {
        mod += m;
    }
    return mod;
}

이렇게하면 분기없이 매우 작은 함수가 생성됩니다.

modulo(int, unsigned int):                            # @modulo(int, unsigned int)
        mov     eax, edi
        cdq
        idiv    esi
        sar     edi, 31
        and     edi, esi
        lea     eax, [rdi + rdx]
        ret

예를 들어 modulo(-5, 7)돌아갑니다 2.

불행히도 몫이 알려지지 않았기 때문에 다른 정수 연산에 비해 약간 느린 정수 분할을 수행해야합니다. 배열의 크기가 2의 제곱이라는 것을 알고 있다면, 컴파일러가 더 효율적인 함수로 최적화 할 수 있도록 이러한 함수 정의를 헤더에 보관하는 것이 좋습니다. 기능은 다음과 같습니다 unsigned modulo256(int v) { return modulo(v,256); }.

modulo256(int):                          # @modulo256(int)
        mov     eax, edi
        sar     eax, 31
        shr     eax, 24
        add     eax, edi
        and     eax, -256
        mov     ecx, edi
        sub     ecx, eax
        shr     edi, 23
        and     edi, 256
        lea     eax, [rdi + rcx]
        ret

어셈블리 참조 : https://gcc.godbolt.org/z/LPdMFS

가장 많이 투표 한 답변과 비교 참조 : http://quick-bench.com/oJbVwLr9G5HJb0oRaYpQOCec4E4

---

내가 배운 표준 방법은

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

이 함수는 본질적으로 abs(사실 잘못된 결과를 반환하는) 없는 첫 번째 변형 입니다. 최적화 컴파일러가이 패턴을 인식하고 "서명되지 않은 모듈로"를 계산하는 기계 코드로 컴파일 할 수 있다면 놀라지 않을 것입니다.

편집하다:

두 번째 변형으로 넘어 가기 : 우선, 버그도 포함되어 n < 0있습니다 i < 0.

이 변형은 분기처럼 보이지 않을 수 있지만 많은 아키텍처에서 i < 0조건부 점프로 컴파일됩니다. 어떤 경우에는, 대체 빨리 적어도 것이다 (n * (i < 0))로 i < 0? n: 0승산을 방지하는; 또한 bool을 int로 재 해석하지 않기 때문에 "더 깨끗"합니다.

As to which of these two variants is faster, that probably depends on the compiler and processor architecture -- time the two variants and see. I don't think there's a faster way than either of these two variants, though.

---

Modulo a power of two, the following works (assuming twos complement representation):

return i & (n-1);

---

An old-school way to get the optional addend using twos-complement sign-bit propagation:

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

---

You can as well do array[(i+array_size*N) % array_size], where N is large enough integer to guarantee positive argument, but small enough for not to overflow.

When the array_size is constant, there are techniques to calculate the modulus without division. Besides of power of two approach, one can calculate a weighted sum of bitgroups multiplied by the 2^i % n, where i is the least significant bit in each group:

e.g. 32-bit integer 0xaabbccdd % 100 = dd + cc*[2]56 + bb*[655]36 + aa*[167772]16, having the maximum range of (1+56+36+16)*255 = 27795. With repeated applications and different subdivision one can reduce the operation to few conditional subtractions.

Common practises also include approximation of division with reciprocal of 2^32 / n, which usually can handle reasonably large range of arguments.

 i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...)

---

Your second example is better than the first. A multiplication is a more complex operation than an if/else operation, so use this:

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

---

If you can afford to promote to a larger type (and do your modulo on the larger type), this code does a single modulo and no if:

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

---

Fastest way to get a positive modulo in C/C++

The following fast? - maybe not as fast as others, yet is simple and functionally correct for all¹ a,b -- unlike others.

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

---

Various other answers have mod(a,b) weaknesses especially when b < 0.

See Euclidean division for ideas about b < 0

---

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

Fails when i % n + n overflows (think large i, n) - Undefined behavior.

---

return i & (n-1);

Relies on n as a power of two. (Fair that the answer does mention this.)

---

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

Often fails when n < 0. e, g, positive_mod(-2,-3) --> -5

---

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

Obliges using 2 integer widths. (Fair that the answer does mention this.)
Fails with modulo < 0. positive_modulo(2, -3) --> -1.

---

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

Often fails when n < 0. e, g, positive_modulo(-2,-3) --> -5

---

¹ Exceptions: In C, a%b is not defined when a/b overflows as in a/0 or INT_MIN/-1.

ReferenceURL : https://stackoverflow.com/questions/14997165/fastest-way-to-get-a-positive-modulo-in-c-c