C/C++에서 %(모듈러스)를 사용할 수 있는 대안이 있습니까?

C/C++에서 %(모듈러스)를 사용할 수 있는 대안이 있습니까?

저는 모듈러스 연산자가 정수 분할 명령이 없는 8비트 마이크로 컨트롤러와 같은 작은 임베디드 장치에서는 비효율적이라는 것을 어디선가 읽은 적이 있습니다.아마 누군가가 확인할 수 있겠지만 정수 분할 작업보다 5-10배 정도 느린 것 같습니다.

카운터 변수를 유지하고 모드 포인트에서 수동으로 0으로 오버플로하는 것 외에 다른 방법이 있습니까?

const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}

vs:

제가 현재 하고 있는 방식:

const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
    if(fizzcount >= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}

아, 약간 현명한 산술의 즐거움.많은 분할 루틴의 부작용은 모듈러스(modulus)입니다. 따라서 실제로 분할이 모듈러스(modulus)보다 빠른 경우는 거의 없습니다.저는 당신이 이 정보를 입수한 출처를 보고 싶습니다.곱셈기를 사용하는 프로세서는 곱셈기를 사용하여 흥미로운 나눗셈 루틴을 갖지만, 나눗셈 결과에서 모듈러스까지 두 단계(곱셈과 뺄셈) 만으로 얻을 수 있으므로 여전히 비교가 가능합니다.프로세서에 내장된 분할 루틴이 있다면 나머지 부분도 제공한다는 것을 알 수 있을 것입니다.

그러나 모듈러스 연산을 최적화하는 방법을 정말로 이해하고 싶다면 연구가 필요한 모듈러 산술에 전념하는 수 이론의 작은 분기가 있습니다.예를 들어, 모듈식 산술은 마법 사각형을 생성하는데 매우 유용합니다.

그런 의미에서, 여기 x의 예에 대한 모듈러스의 수학에 대한 매우 낮은 수준의 예가 있습니다. 이것은 나눗셈과 비교하여 얼마나 단순할 수 있는지 보여줄 것입니다.

---

아마도 그 문제를 생각하는 더 좋은 방법은 숫자 베이스와 모듈로 산술의 관점일 것입니다.예를 들어, DOW가 요일의 16비트 표현인 DOW mod 7을 계산하는 것이 목표입니다.다음과 같이 쓸 수 있습니다.

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

이렇게 표현하면 높은 바이트와 낮은 바이트에 대한 모듈로 7 결과를 별도로 계산할 수 있습니다.높은 값에 4를 곱하여 낮은 값에 더한 다음 결과 모듈로 7을 계산합니다.

8비트 숫자의 mod 7 결과를 계산하는 것도 비슷한 방법으로 수행될 수 있습니다.다음과 같이 8비트 숫자를 8진수로 쓸 수 있습니다.

  X = a*64 + b*8 + c

여기서 a, b, c는 3비트 숫자입니다.

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

64%7 = 8%7 = 1

당연하죠, a,b,care.

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

한 의 가능한 값a+b+c이다 ㅇ7+7+3 = 17 더 합니다. 그래서 팔자걸음이 하나 더 필요합니다.되지 않은) C은 다음과같이 쓸 수 :되지 은은 ) C과이쓸다수한다수쓸은:eeen이과d한지(et

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

저는 PIC 버전을 쓰느라 잠시 시간을 보냈습니다.실제 구현은 위에서 설명한 것과 약간 다릅니다.

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

여기 알고리즘을 테스트하기 위한 간단한 루틴이 있습니다.

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

마지막으로 (테스트하지 않은) 16비트 결과에 대해 다음과 같이 쓸 수 있습니다.

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

스캇

---

숫자 모드를 2의 거듭제곱으로 계산하는 경우 비트 단위 및 연산자를 사용할 수 있습니다.두 번째 숫자에서 하나만 빼면 됩니다.예를 들어,

x % 8 == x & 7
x % 256 == x & 255

몇 가지 주의 사항:

1. 이것은 두 번째 숫자가 2의 거듭제곱인 경우에만 작동합니다.
2. 모듈러스가 항상 양수일 경우에만 동등합니다.C와 C++ 표준은 첫 번째 숫자가 음수일 때 모듈러스의 부호를 지정하지 않습니다(대부분의 컴파일러가 이미 수행하고 있던 것인 C++11까지는 음수임을 보장합니다).부호 비트를 비트 단위로 제거하면 항상 양수(즉, 나머지가 아닌 참 계수)가 됩니다.어쨌든 그게 당신이 원하는 것처럼 들립니다.
3. 컴파일러는 이미 가능할 때 이 작업을 수행하고 있으므로 대부분의 경우 수동으로 수행할 가치가 없습니다.

모듈로를 사용할 때 대부분의 경우 2의 거듭제곱이 아닌 오버헤드가 발생합니다.모듈러스 연산자를 가진 프로세서라도 마스크 연산에 비해 분할 시 몇 사이클이 느리기 때문에 이는 프로세서와 관계가 없습니다.

대부분의 경우 이는 고려할 가치가 있는 최적화가 아니며, (특히 분할 또는 곱하기가 여전히 포함된 경우) 자신의 단축 연산을 계산할 가치가 없는 것은 분명합니다.

그러나 경험칙 중 하나는 배열 크기 등을 2의 거듭제곱으로 선택하는 것입니다.

따라서 요일을 계산할 경우 약 100개 항목의 순환 버퍼를 설정하는 경우에도 상관없이 %7을 사용할 수 있습니다.128로 하는게 어때요?그러면 % 128을 쓸 수 있고 대부분의 (모든) 컴파일러가 이 & 0x7F를 만들 것입니다.

여러 임베디드 플랫폼에서 고성능이 필요한 경우가 아니라면 프로필을 작성하기 전까지는 성능상의 이유로 코드를 작성하는 방법을 변경하지 마십시오.

성능을 최적화하기 위해 어색하게 작성된 코드는 디버깅하기 어렵고 유지보수하기 어렵습니다.테스트 케이스를 작성하고 목표물에 프로파일링합니다.모듈러스의 실제 비용을 알고 나면 대체 솔루션이 코딩할 가치가 있는지 여부를 결정합니다.

@매튜 말이 맞습니다.시도해 보기:

int main() {
  int i;
  for(i = 0; i<=1024; i++) {
    if (!(i & 0xFF)) printf("& i = %d\n", i);
    if (!(i % 0x100)) printf("mod i = %d\n", i);
  }
}

x%y == (x-(x/y)*y)

도움이 되길 바랍니다.

내장된 장치에서 프로그래밍 가능한 하드웨어에 액세스할 수 있습니까?카운터 같은 거?그렇다면 시뮬레이션 %를 사용하는 대신 하드웨어 기반 모드 단위를 작성할 수 있습니다. (VHDL에서 한 번 해봤습니다. 코드가 아직 있는지는 잘 모르겠습니다.)

명심하세요, 분열 속도가 5배에서 10배 빠르다고 하셨잖아요.모드 시뮬레이션을 위해 분할, 곱셈, 뺄셈을 고려해보셨나요? (편집: 원래 게시물을 잘못 이해하였습니다.mod보다 division이 빠르다는 것이 이상하다고 생각했습니다, 같은 작업입니다.)

그러나 특정한 경우에는 6.6 = 2*3의 모드를 확인하고 있습니다.따라서 최소값이 0인지 먼저 확인하면 약간의 이득을 얻을 수 있습니다.

if((!(x & 1)) && (x % 3))
{
    print("Fizz\n");
}

하지만 그렇게 한다면 당신이 얻을 수 있는 것이 있는지 확인해 보는 것이 좋습니다. 프로파일러들도 그렇습니다.댓글 달기도 하고 있어요.그렇지 않으면 코드를 봐야 하는 다음 사람이 불쌍할 겁니다.

당신은 당신이 필요로 하는 임베디드 기기를 정말로 확인해야 합니다.내가 본 모든 어셈블리 언어(x86, 68000)는 나눗셈을 사용하여 모듈러스를 구현합니다.

실제로 분할 조립 작업은 분할 결과를 반환하고 나머지는 두 개의 서로 다른 레지스터에 저장합니다.

"모듈러스" 연산과 "모듈러스" 잘입니다.&,|ㅇ>>.

@Jeff V: 문제가 있는 것 같습니다! (원래 코드가 mod 6을 찾고 있었고 이제는 본질적으로 mod 8을 찾고 있습니다.)계속 +1을 더 합니다.당신의 컴파일러가 그것을 최적화하기를 바라지만, 2에서 테스트 시작해서 MAXCOUNT 포함으로 가는 것은 어떨까요?마지막으로 (x+1)이 8로 분할되지 않을 때마다 참으로 반환됩니다.그게 네가 원하는 거니?(그렇다고 가정하지만, 확인하고 싶습니다.)

modulo 6의 경우 Python 코드를 C/C++로 변경할 수 있습니다.

def mod6(number):
    while number > 7:
        number = (number >> 3 << 1) + (number & 0x7)
    if number > 5:
        number -= 6
    return number

더 좋은 , 이 은 를 은 를 이 은 FIZZ한 횟수만큼 만큼 하는 가 가 만큼 하는 Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ, Δ ΔMAXCOUNT에 의해 균등하게 분할되지 않습니다.FIZZ.

그렇기는 하지만, 귀사가 겪고 있는 성능 제약 조건에 대해 명확하게 파악하기 위해 의도된 플랫폼에 대한 조사 및 성능 프로파일링을 실시하는 것이 좋습니다.최적화 작업에 사용할 수 있는 생산성이 훨씬 더 높아질 수 있습니다.

인쇄문은 모듈러스 연산자를 가장 느리게 구현하는 것보다 훨씬 더 긴 시간이 소요됩니다.따라서 기본적으로 "일부 시스템에서 느리다"는 코멘트는 "모든 시스템에서 느리다"는 것이어야 합니다.

또한 제공된 두 개의 코드 조각은 동일한 작업을 수행하지 않습니다.두번째로, 그 라인은

if(fizzcount >= FIZZ)

항상 거짓이다 그래서"FIZZ\n"은 인쇄되지 않습니다.

언급URL : https://stackoverflow.com/questions/48053/is-there-any-alternative-to-using-modulus-in-c-c