곱하기 + 시프트 (32 비트) 곱하기 + 나눗셈

Question

비율 계산을 수행하는 가장 빠른 방법은 y = x * a/b입니다. 모든 값은 부호가없고 32 비트이고 a 및 b은 고정되어 있습니다 (한 번 초기화 됨 , 그리고 나서 변경하지 않음) 컴파일 타임에 알려지지 않았습니다. 결과는 오버 플로우되지 않도록 보장됩니다 (심지어 중간 곱셈이 64 비트를 필요로한다고 생각할지라도). 프로그래밍 언어는 그다지 중요하지 않지만 Java가 내 경우에 가장 적합 할 것입니다. 가능한 한 빨리해야합니다 (나노초 문제). 현재 사용 중 :

int result = (int) ((long) x * a/b); 

하지만 분류가 느립니다. 그래서 가장 좋은 유형의 공식 것, 약 Perform integer division using multiplication 알고

factor 및 shift이 a 및 b (즉, 계산 속도가 느려질 수 있습니다)로부터 계산 될 수있다

int result = (int) (((long) x * factor) >>> shift); 

.

는 단순히 원래 식의 분할 부품을 교체하려고했으나이 곱셈의 결과가 64 비트에 맞지 않기 때문에 작동하지 않습니다 :

// init 
int shift = 63 - Integer.numberOfLeadingZeros(b); 
int factor = ((1L << shift)/b) + 1; 
... 
// actual calculation 
int result = (int) ((long) x * a * factor) >>> shift); 

결과는하지 않습니다 실제로 내 경우에는 완전히 정확해야한다. (하나는 괜찮을 것이다.)

Answer 1

어떤 준비를 위해

long a2 = a & 0xFFFFFFFFL; 
long b2 = b & 0xFFFFFFFFL; 
checkArgument(b2 > 0); 
double dFactor = (double) a2/b2; 
shift = 0; 
while (dFactor < 1L<<32) { 
    dFactor *= 2; 
    shift++; 
} 
factor = (long) dFactor; 

와 빠른 부분

int result = (int) (((x & 0xFFFFFFFFL) * factor) >>> shift); 

어떻습니까? 이제 2**32 <= factor < 2**33이고 int x >= 0 인 경우 제품 x * factor < 2**31 * 2**33 = 2**64은 unsigned long에 딱 들어 맞습니다. 어떤 비트도 낭비되지 않습니다. dFactor에서 long으로의 전환은 차선이 될 수 있습니다.

---

준비가 확실하게 빨라질 수 있습니다. 특히, 앞에 오는 0부터 먼저 루프를 제거하면됩니다. 나는 그것들을 단순하게 만들면서 double을 제거하는 것을 귀찮게하지 않을 것이다.

Answer 2

a 이후와 b 모두가 고정되어, (이 이미 무대 뒤에서 자동으로 발생 될 수 있습니다) 한 번 분열을하고 결과를 다시 바로 수 :

int c = a/b; 
int y1 = x1 * c; 
int y2 = x2 * c; 
... 

당신이 정말로 그것을 최적화해야하는 경우, GPU (예 : CUDA의 경우 Java 바인딩 사용)을 실행하여 계산을 병렬 처리 할 수 ​​있습니다. 구현하기가 훨씬 까다 롭습니다.

마지막으로, 테스트 할 때 타이머를 추가하여 벤치 마크를 실행하여 최적화로 인해 성능이 실제로 향상되는지 확인하는 것이 좋습니다.

Answer 3

수식 (x * factor) >>> shift을 사용하는 경우 항상 정확한 결과를 얻을 수 없다고 생각합니다. 일부 엣지의 경우 결과가 너무 낮거나 1이 너무 높습니다. 항상 올바른 결과를 얻으려면 수식이 더 복잡해야합니다.부동 소수점을 필요로하지 않는 솔루션을 찾았습니다. 여기에 테스트 케이스가 있습니다 :

static final Set<Integer> SOME_VALUES = new TreeSet<Integer>(); 

static { 
    Set<Integer> set = SOME_VALUES; 
    for (int i = 0; i < 100; i++) { 
     set.add(i); 
    } 
    set.add(Integer.MAX_VALUE); 
    set.add(Integer.MAX_VALUE - 1); 
    for (int i = 1; i > 0; i += i) { 
     set.add(i - 1); 
     set.add(i); 
     set.add(i + 1); 
    } 
    for (int i = 1; i > 0; i *= 3) { 
     set.add(i); 
    } 
    Random r = new Random(1); 
    for (int i = 0; i < 100; i++) { 
     set.add(r.nextInt(Integer.MAX_VALUE)); 
    } 
} 

private static void testMultiplyDelete() { 
    for (int a : SOME_VALUES) { 
     for (int b : SOME_VALUES) { 
      if (b == 0) { 
       continue; 
      } 
      int shift = 32; 
      // sometimes 1 too low 
      long factor = (1L << shift) * a/b; 
      // sometimes 1 too high 
      // long factor = ((1L << shift) * a/b) + 1; 

      // sometimes 1 too low 
      // double dFactor = (double) a/b; 
      // int shift = 0; 
      // while (dFactor > 0 && dFactor < (1L << 32)) { 
      //  dFactor *= 2; 
      //  shift++; 
      // } 
      // long factor = (long) dFactor; 

      for (int x : SOME_VALUES) { 
       long expectedResult = (long) x * a/b; 
       if (expectedResult < 0 || 
         expectedResult >= Integer.MAX_VALUE) { 
        continue; 
       } 
       int result = (int) ((x * factor) >>> shift); 
       if (Math.abs(result - expectedResult) > 1) { 
        System.out.println(x + "*" + a + "/" + b + 
          "=" + expectedResult + "; " + 
          "(" + x + "*" + factor + ")>>>" + shift + "=" + result); 
       } 
      } 
     } 
    } 
}