정수를 3으로 나누는 가장 빠른 방법은 무엇입니까?

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

문제 

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication
도움이 되었습니까?

해결책

이것은 컴파운드 프로세서에 따라 컴파일러가 최적화 할 수 있으므로 가장 빠릅니다.

int a;
int b;

a = some value;
b = a / 3;

다른 팁

"컴파일러에 맡기십시오"라고 말한 사람은 옳았지만, 그를 수정하거나 댓글을달라고 "평판"이 없습니다. GCC를 요청하여 int test (int a) {return a / 3; } ix86의 경우 출력을 분해했습니다. 학문적 관심을 위해서만하고있는 일은 대충 0x55555556을 곱한 다음 64 비트 결과의 상위 32 비트를 가져옵니다. 예를 들어 다음과 같이 이것을 보여줄 수 있습니다.

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$

Wikipedia 페이지 on 몽고메리 사업부 읽기가 어렵지만 다행히도 컴파일러 직원이 해냈으므로 필요하지 않습니다.

예를 들어, 서명 된 정수를 3으로 나누고 나누는 값의 범위가 0에서 768이라는 것을 알고 있다면 값의 범위를 알고 있다면 더 빠른 방법이 있습니다. 요인에 의해, 2의 전력에 의해 왼쪽으로 옮겨지는 요인을 3으로 나눈다.

예를 들어.

범위 0-> 768

1024를 곱하는 10 비트의 이동을 사용할 수 있습니다. 1024로 나누려서 승수는 1024 / 3 = 341이어야합니다.

이제 사용할 수 있습니다 (X * 341) >> 10
(서명 된 정수를 사용하는 경우 시프트가 서명 된 시프트인지 확인하십시오) 또한 시프트가 실제로 시프트이며 비트 롤이 아닌지 확인하십시오.

이것은 값 3을 효과적으로 나누고 표준 x86 / x64 CPU에서 자연적인 분할 속도의 약 1.6 배로 실행됩니다.

물론 컴파일러가 할 수있을 때이 최적화를 할 수있는 유일한 이유는 컴파일러가 X의 최대 범위를 알지 못 하므로이 결정을 할 수 없지만 프로그래머로서 할 수 있기 때문입니다.

언젠가는 값을 더 큰 값으로 옮기고 같은 일을하는 것이 더 유익 할 수도 있습니다. 전체 범위의 int가있는 경우 64 비트 값으로 만들고 3으로 나누는 대신 곱하기 및 변속을 수행 할 수 있습니다.

최근 이미지 처리 속도를 높이기 위해이 작업을 수행해야했는데, 평균 3 개의 컬러 채널, 각 색상 채널을 바이트 범위 (0-255)를 찾아야했습니다. 붉은 녹색과 파란색.

처음에는 단순히 사용했습니다.

avg = (r + g + b) / 3;

(따라서 R + G + B는 최대 768이고 최소 0은 각 채널이 바이트 0-255이기 때문에)

수백만 개의 반복 후 전체 작업은 36 밀리 초가 걸렸습니다.

라인을 다음으로 변경했습니다.

avg = (r + g + b) * 341 >> 10;

그리고 그것은 22 밀리 초로 줄었습니다.

이 속도는 최적화가 켜져 있고 IDE를 통해서가 아니라 디버깅 정보없이 기본적으로 프로그램을 실행하고 있었음에도 불구하고 C#에서 발생했습니다.

보다 3으로 나누는 방법 보다 효율적으로 3으로 나누는 것에 대한 확장 된 논의를 위해 FPGA 산술 작업에 중점을 두었습니다.

또한 관련성 :

플랫폼과 C 컴파일러에 따라 다음과 같은 기본 솔루션을 사용합니다.

y = x / 3

빠르거나 매우 느릴 수 있습니다(나눗셈이 하드웨어에서 완전히 수행되더라도 DIV 명령을 사용하여 수행되는 경우 이 명령은 최신 CPU의 곱셈보다 약 3~4배 느립니다).최적화 플래그가 켜져 있는 매우 우수한 C 컴파일러는 이 작업을 최적화할 수 있지만 확실하게 확인하려면 직접 최적화하는 것이 좋습니다.

최적화를 위해서는 알려진 크기의 정수를 갖는 것이 중요합니다.C에서는 int에 알려진 크기가 없으므로(플랫폼과 컴파일러에 따라 다를 수 있음) C99 고정 크기 정수를 사용하는 것이 좋습니다.아래 코드에서는 부호 없는 32비트 정수를 3으로 나누고 C 컴파일러가 64비트 정수에 대해 알고 있다고 가정합니다(메모:32비트 CPU 아키텍처에서도 대부분의 C 컴파일러는 64비트 정수를 잘 처리할 수 있습니다.):

static inline uint32_t divby3 (
    uint32_t divideMe
) {
    return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}

이상하게 들릴 수도 있지만 위의 방법은 실제로 3으로 나눕니다.이를 위해 필요한 것은 단일 64비트 곱셈과 시프트뿐입니다(앞서 말했듯이 곱셈은 CPU의 나눗셈보다 3~4배 빠를 수 있습니다).64비트 응용 프로그램에서 이 코드는 32비트 응용 프로그램보다 훨씬 빠릅니다(32비트 응용 프로그램에서 두 개의 64비트 숫자를 곱하려면 32비트 값에 대해 3번의 곱셈과 3번의 덧셈이 필요함). 그러나 여전히 32비트 응용 프로그램보다 더 빠를 수 있습니다. 32비트 컴퓨터에서 나누기

반면에, 귀하의 컴파일러가 매우 훌륭하고 상수로 정수 나누기를 최적화하는 방법을 알고 있다면(최신 GCC는 알고 있습니다. 방금 확인했습니다) 어쨌든 위의 코드를 생성할 것입니다(GCC는 다음을 위해 정확히 이 코드를 생성합니다). 최적화 수준 1 이상을 활성화하는 경우 "/3").다른 컴파일러의 경우...이 방법이 매우 잘 문서화되어 있고 인터넷의 모든 곳에서 언급되어 있음에도 불구하고 그러한 트릭을 사용할 것이라고 기대하거나 기대할 수는 없습니다.

문제는 상수에만 작동하고 변수에는 작동하지 않는다는 것입니다.항상 매직 넘버(여기서는 0xAAAAAAAB)와 곱셈(대부분의 경우 시프트 및/또는 덧셈) 후의 올바른 연산을 알아야 하며 둘 다 나누려는 숫자에 따라 다르며 둘 다 CPU 시간이 너무 많이 걸립니다. 즉석에서 계산합니다(하드웨어 분할보다 속도가 느림).그러나 컴파일러가 컴파일 시간 동안 이를 계산하는 것은 쉽습니다(1초 정도의 컴파일 시간은 거의 역할을 하지 않습니다).

당신이라면 어떨까요? 진짜 곱하거나 나누고 싶지 않습니까? 여기에 내가 방금 발명 한 근사치가 있습니다. (x/3) = (x/4) + (x/12)이기 때문에 작동합니다. 그러나 (x/12) = (x/4)/3이므로 프로세스가 충분히 좋을 때까지 반복해야합니다.

#include <stdio.h>

void main()
{
    int n = 1000;
    int a,b;
    a = n >> 2;
    b = (a >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    b = (b >> 2);
    a += b;
    printf("a=%d\n", a);
}

결과는 330입니다. b = ((b+2) >> 2)를 사용하여 더 정확하게 만들 수 있습니다. 반올림을 설명합니다.

만약 너라면 ~이다 곱할 수있게되면, 2 개의 제수 전원으로 (1/3)에 적합한 근사치를 선택하십시오. 예를 들어, n * (1/3) ~ = n * 43 / 128 = (n * 43) >> 7.

이 기술은 가장 유용합니다 인디애나.

더 빠른지는 모르겠지만 약간의 운영자를 사용하여 바이너리 부문을 수행하려면 이 페이지:

  • 지수를 0으로 설정하십시오
  • 배당금과 제수로 가장 왼쪽 숫자를 정렬하십시오
  • 반복하다:
    • 제수 위의 배당의 해당 부분이 디바이저보다 크거나 동일하다면 :
      • 그런 다음 배당금 부분에서 제수를 빼고
      • 몫의 오른쪽 끝에 1을 연결하십시오.
      • 몫의 오른쪽 끝까지 0과 함께
    • 제수를 한 곳으로 바꾸십시오
  • 배당금이 제수보다 작을 때까지 :
  • 몫은 정확하고 배당금은 나머지입니다
  • 멈추다

64 비트 숫자 :

uint64_t divBy3(uint64_t x)
{
    return x*12297829382473034411ULL;
}

그러나 이것은 당신이 기대할 수있는 잘린 정수 부서가 아닙니다. 숫자가 이미 3으로 나눌 수있는 경우 올바르게 작동하지만 그렇지 않으면 막대한 숫자를 반환합니다.

예를 들어, 예를 들어 11에서 실행하면 6148914691236517209를 반환합니다. 이것은 쓰레기처럼 보이지만 실제로 정답입니다. 3을 곱하면 11을 되 찾으십시오!

잘린 부문을 찾고 있다면 / 연산자 만 사용하십시오. 나는 당신이 그보다 훨씬 빨리 얻을 수 있다는 것을 의심합니다.

이론:

64 비트 서명되지 않은 산술은 모듈로 2^64 산술입니다. 이것은 2^64 모듈러스 (본질적으로 모든 홀수 숫자)를 갖는 공로 인 각 정수를 의미합니다. 이 마법 번호는 해결하여 얻을 수 있습니다 3*x + 2^64*y = 1 확장 된 유클리드 알고리즘을 사용한 방정식.

이 기사를 정말로보고 싶다면 정수 부서, 그러나 그것은 학문적 장점 만 가지고 있습니다 ... 그런 종류의 속임수로부터 혜택을받는 것은 실제로 수행 해야하는 흥미로운 응용 프로그램 일 것입니다.

실제로 큰 정수 부서 (예 : 64 비트보다 큰 숫자)의 경우 숫자를 int []로 표시하고 한 번에 두 자리 숫자를 가져 와서 3으로 나누어서 매우 빨리 부문을 수행 할 수 있습니다. 나머지는 다음 두 자리의 일부가됩니다. 기타 등등.

예를 들어. 11004 / 3 당신은 말한다

11/3 = 3, 남아 = 2 (11-3*3)

20/3 = 6, 나머지 = 2 (20-6*3)

20/3 = 6, 나머지 = 2 (20-6*3)

24/3 = 8, 나머지 = 0

따라서 결과 3668

internal static List<int> Div3(int[] a)
{
  int remainder = 0;
  var res = new List<int>();
  for (int i = 0; i < a.Length; i++)
  {
    var val = remainder + a[i];
    var div = val/3;

    remainder = 10*(val%3);
    if (div > 9)
    {
      res.Add(div/10);
      res.Add(div%10);
    }
    else
      res.Add(div);
  }
  if (res[0] == 0) res.RemoveAt(0);
  return res;
}

쉬운 계산 ... 대부분의 N 반복에서 N은 비트 수입니다.

uint8_t divideby3(uint8_t x)
{
  uint8_t answer =0;
  do
  {
    x>>=1;
    answer+=x;
    x=-x;
  }while(x);
  return answer;
}

일부 아키텍처에서는 조회 테이블 접근 방식이 더 빠릅니다.

uint8_t DivBy3LU(uint8_t u8Operand)
{
   uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];

   return ai8Div3[u8Operand];
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top