Multiply + Divide, используя только Multiply + Shift (32 бит)

Question

Я хотел бы узнать самый быстрый способ вычисления пропорций, то есть y = x * a/b, где все значения 32 бит, без знака и a и b являются фиксированными (инициализируется один раз , а затем не изменяются), но не известны во время компиляции. Результат гарантированно не переполняется (даже подумал, что промежуточное умножение может понадобиться 64 бит). Язык программирования не имеет большого значения, но Java лучше всего подходит для моего случая. Это должно быть как можно быстрее (наносекунда). В настоящее время я использую:

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

Но разделение происходит медленно. Я знаю о Perform integer division using multiplication, так что лучше бы формула типа:

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

где factor и shift могут быть вычислены из a и b (что расчет может быть медленным).

Я попытался просто заменить часть деления исходной формулы, но она не работает, так как результат двух умножений не помещаются в 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 округляет, что может быть неоптимальным.

---

препарат, безусловно, может быть ускорено, особенно цикл может быть устранен, глядя на ведущие нули первой. Я бы не стал беспокоиться об устранении double, поскольку это делает вещи простыми.

Answer 2

С a и b оба фиксированы, вы можете просто сделать разделение раз и повторно использовать результат (это может быть уже происходит автоматически за кадром):

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

Если вам действительно нужно, чтобы оптимизировать его, запустите его на GPU (например, используя привязки java для CUDA), что позволит вам распараллелить вычисления, хотя это намного сложнее реализовать.

И, наконец, всегда рекомендуется добавлять таймеры при тестировании, чтобы вы могли запускать тесты, чтобы убедиться, что оптимизация фактически повышает производительность.

Answer 3

Я думаю, что невозможно всегда получить точный результат, если использовать формулу (x * factor) >>> shift: для некоторых случаев с краями результат 1 слишком низок или 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); 
       } 
      } 
     } 
    } 
}