(a * b) / c MulDiv и работа с переполнением при промежуточном умножении

Question

Мне нужно сделать следующую арифметику:

long a,b,c;
long result = a*b/c;

Хотя результат гарантированно помещается в long, умножение - нет, поэтому оно может переполниться.

Я попытался сделать это шаг за шагом (сначала умножить, а затем разделить), имея дело с переполнением, разделив промежуточный результат a*b на массив int размером не более 4 (так же, как BigInteger использует int[] mag переменная).

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

Гипотетический метод будет:

public static long divide(int[] dividend, long divisor)

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

Любая помощь будет высоко ценится!

Edit: Я не пытаюсь реализовать весь BigInteger сам. Я пытаюсь решить конкретную проблему (a*b/c, где a*b может переполниться) быстрее, чем использование универсального BigInteger.

Edit2: было бы идеально, если бы это можно было сделать умным 1028 * способом, вообще не допуская переполнения, некоторые комментарии всплыли в комментариях, но я все еще ищу тот, который является правильным.

Обновление: Я попытался портировать код BigInteger для своих конкретных нужд, без создания объектов, и на первой итерации я получил улучшение скорости на ~ 46% по сравнению с использованием BigInteger (на моем компьютере для разработки).

Затем я попробовал немного модифицированное решение @David Eisenstat, которое дало мне ~ 56% (я выполнил 100_000_000_000 случайных входов от Long.MIN_VALUE до Long.MAX_VALUE) сокращенное время выполнения (более чем в 2 раза) по сравнению с BigInteger (то есть ~ 18% по сравнению с моим адаптированным алгоритмом BigInteger).

Будет больше итераций по оптимизации и тестированию, но на данный момент, я думаю, я должен принять этот ответ как лучший.

Answer 1

Дэвид Эйзенстат заставил меня задуматься.
Я хочу, чтобы простые дела были быстрыми: пусть об этом позаботится double. Ньютон-Рафсон может быть лучшим выбором для остальных.

 /** Multiplies both <code>factor</code>s
  *  and divides by <code>divisor</code>.
  * @return <code>Long.MIN_VALUE</code> if result out of range,<br/>
  *     else <code>factorA * factor1 / divisor</code> */
    public static long
    mulDiv(long factorA, long factor1, long divisor) {
        final double dd = divisor,
            product = (double)factorA * factor1,
            a1_d = product / dd;
        if (a1_d < -TOO_LARGE || TOO_LARGE < a1_d)
            return tooLarge();
        if (-ONE_ < a1_d && a1_d < ONE_)
            return 0;
        if (-EXACT < product && product < EXACT)
            return (long) a1_d;
        long pLo = factorA * factor1, //diff,
            pHi = high64(factorA, factor1);
        if (a1_d < -LONG_MAX_ || LONG_MAX_ < a1_d) {
            long maxdHi = divisor >> 1;
            if (maxdHi < pHi
                || maxdHi == pHi
                   && Long.compareUnsigned((divisor << Long.SIZE-1),
                                           pLo) <= 0)
                return tooLarge();
        }
        final double high_dd = TWO_POWER64/dd;
        long quotient = (long) a1_d,
            loPP = quotient * divisor,
            hiPP = high64(quotient, divisor);
        long remHi = pHi - hiPP, // xxx overflow/carry
            remLo = pLo - loPP;
        if (Long.compareUnsigned(pLo, remLo) < 0)
            remHi -= 1;
        double fudge = remHi * high_dd;
        if (remLo < 0)
            fudge += high_dd;
        fudge += remLo/dd;
        long //fHi = (long)fudge/TWO_POWER64,
            fLo = (long) Math.floor(fudge); //*round
        quotient += fLo;
        loPP = quotient * divisor;
        hiPP = high64(quotient, divisor);
        remHi = pHi - hiPP; // should be 0?!
        remLo = pLo - loPP;
        if (Long.compareUnsigned(pLo, remLo) < 0)
            remHi -= 1;
        if (0 == remHi && 0 <= remLo && remLo < divisor)
            return quotient;

        fudge = remHi * high_dd;
        if (remLo < 0)
            fudge += high_dd;
        fudge += remLo/dd;
        fLo = (long) Math.floor(fudge);
        return quotient + fLo;
    }

 /** max <code>double</code> trusted to represent
  *  a value in the range of <code>long</code> */
    static final double
        LONG_MAX_ = Double.valueOf(Long.MAX_VALUE - 0xFFF);
 /** max <code>double</code> trusted to represent a value below 1 */
    static final double
        ONE_ = Double.longBitsToDouble(
                    Double.doubleToRawLongBits(1) - 4);
 /** max <code>double</code> trusted to represent a value exactly */
    static final double
        EXACT = Long.MAX_VALUE >> 12;
    static final double
        TWO_POWER64 = Double.valueOf(1L<<32)*Double.valueOf(1L<<32);

    static long tooLarge() {
//      throw new RuntimeException("result too large for long");
        return Long.MIN_VALUE;
    }
    static final long   ONES_32 = ~(~0L << 32);

    static long high64(long factorA, long factor1) {
        long loA = factorA & ONES_32,
            hiA = factorA >>> 32,
            lo1 = factor1 & ONES_32,
            hi1 = factor1 >>> 32;
        return ((loA * lo1 >>> 32)
                +loA * hi1 + hiA * lo1 >>> 32)
               + hiA * hi1;
    }

(Я немного переставил этот код из IDE, чтобы mulDiv() был сверху. Будучи ленивым, у меня есть обертка для обработки знаков - может попытаться сделать это правильно, пока ад не замерзнет.
Для синхронизации крайне необходима модель ввода:
Как насчет , так что каждый возможный результат одинаково вероятен ?)

Answer 2

Я возился с подходом, который (1) умножает a и b со школьным алгоритмом на 21-битных конечностях (2), продолжает делать длинное деление на c с необычным представлением остаток a*b - c*q, который использует double для хранения битов старшего разряда и long для хранения битов младшего разряда. Я не знаю, можно ли его сделать конкурентоспособным со стандартным длинным делением, но для вашего удовольствия,

public class MulDiv {
  public static void main(String[] args) {
    java.util.Random r = new java.util.Random();
    for (long i = 0; true; i++) {
      if (i % 1000000 == 0) {
        System.err.println(i);
      }
      long a = r.nextLong() >> (r.nextInt(8) * 8);
      long b = r.nextLong() >> (r.nextInt(8) * 8);
      long c = r.nextLong() >> (r.nextInt(8) * 8);
      if (c == 0) {
        continue;
      }
      long x = mulDiv(a, b, c);
      java.math.BigInteger aa = java.math.BigInteger.valueOf(a);
      java.math.BigInteger bb = java.math.BigInteger.valueOf(b);
      java.math.BigInteger cc = java.math.BigInteger.valueOf(c);
      java.math.BigInteger xx = aa.multiply(bb).divide(cc);
      if (java.math.BigInteger.valueOf(xx.longValue()).equals(xx) && x != xx.longValue()) {
        System.out.printf("a=%d b=%d c=%d: %d != %s\n", a, b, c, x, xx);
      }
    }
  }

  // Returns truncate(a b/c), subject to the precondition that the result is
  // defined and can be represented as a long.
  private static long mulDiv(long a, long b, long c) {
    // Decompose a.
    long a2 = a >> 42;
    long a10 = a - (a2 << 42);
    long a1 = a10 >> 21;
    long a0 = a10 - (a1 << 21);
    assert a == (((a2 << 21) + a1) << 21) + a0;
    // Decompose b.
    long b2 = b >> 42;
    long b10 = b - (b2 << 42);
    long b1 = b10 >> 21;
    long b0 = b10 - (b1 << 21);
    assert b == (((b2 << 21) + b1) << 21) + b0;
    // Compute a b.
    long ab4 = a2 * b2;
    long ab3 = a2 * b1 + a1 * b2;
    long ab2 = a2 * b0 + a1 * b1 + a0 * b2;
    long ab1 = a1 * b0 + a0 * b1;
    long ab0 = a0 * b0;
    // Compute a b/c.
    DivBy d = new DivBy(c);
    d.shift21Add(ab4);
    d.shift21Add(ab3);
    d.shift21Add(ab2);
    d.shift21Add(ab1);
    d.shift21Add(ab0);
    return d.getQuotient();
  }
}

public strictfp class DivBy {
  // Initializes n <- 0.
  public DivBy(long d) {
    di = d;
    df = (double) d;
    oneOverD = 1.0 / df;
  }

  // Updates n <- 2^21 n + i. Assumes |i| <= 3 (2^42).
  public void shift21Add(long i) {
    // Update the quotient and remainder.
    q <<= 21;
    ri = (ri << 21) + i;
    rf = rf * (double) (1 << 21) + (double) i;
    reduce();
  }

  // Returns truncate(n/d).
  public long getQuotient() {
    while (rf != (double) ri) {
      reduce();
    }
    // Round toward zero.
    if (q > 0) {
      if ((di > 0 && ri < 0) || (di < 0 && ri > 0)) {
        return q - 1;
      }
    } else if (q < 0) {
      if ((di > 0 && ri > 0) || (di < 0 && ri < 0)) {
        return q + 1;
      }
    }
    return q;
  }

  private void reduce() {
    // x is approximately r/d.
    long x = Math.round(rf * oneOverD);
    q += x;
    ri -= di * x;
    rf = repairLowOrderBits(rf - df * (double) x, ri);
  }

  private static double repairLowOrderBits(double f, long i) {
    int e = Math.getExponent(f);
    if (e < 64) {
      return (double) i;
    }
    long rawBits = Double.doubleToRawLongBits(f);
    long lowOrderBits = (rawBits >> 63) ^ (rawBits << (e - 52));
    return f + (double) (i - lowOrderBits);
  }

  private final long di;
  private final double df;
  private final double oneOverD;
  private long q = 0;
  private long ri = 0;
  private double rf = 0;
}

Answer 3

Разделите A / C и B / C на целые и дробные (остаток) части, тогда у вас есть:

a*b/c 
= c * a/c * b/c 
= c * (x/c + y/c) * (z/c + w/c)
= xz/c + xw/c + yz/c + yw/c where x and z are multiples of c

Таким образом, вы можете тривиально вычислить первые три фактора без переполнения. По моему опыту, этого достаточно, чтобы покрыть типичные случаи переполнения. Однако, если ваш делитель слишком велик, так что (a % c) * (b % c) переполняется, этот метод все равно не работает. Если это типичная проблема для вас, вы можете рассмотреть другие подходы (например, деление как наибольшего из a и b, так и c на 2, пока у вас больше не будет переполнений, но как это сделать, не внося дополнительную ошибку из-за предвзятость в этом процессе нетривиальна - вам нужно будет сохранить текущий счет ошибки в отдельной переменной, вероятно)

В любом случае, код для вышеперечисленного:

long a,b,c;
long bMod = (b % c)
long result = a * (b / c) + (a / c) * bMod + ((a % c) * bMod) / c;

Если скорость представляет большую проблему (я предполагаю, что она хотя бы в некоторой степени, поскольку вы спрашиваете об этом), вы можете рассмотреть возможность хранения a/c и b/c в переменных и вычисления мода через умножение, например заменить (a % c) на (a - aDiv * c) - это позволяет перейти от 4 делений за вызов к 2.

Answer 4

Вы можете использовать наибольший общий делитель (gcd), чтобы помочь.

a * b / c = (a / gcd(a,c)) * (b / (c / gcd(a,c)))

Редактировать: ОП попросил меня объяснить вышеприведенное уравнение. В основном имеем:

a = (a / gcd(a,c)) * gcd(a,c)
c = (c / gcd(a,c)) * gcd(a,c)

Let's say x=gcd(a,c) for brevity, and rewrite this.

a*b/c = (a/x) * x * b 
        --------------
        (c/x) * x

Next, we cancel

a*b/c = (a/x) * b 
        ----------
        (c/x) 

Вы можете сделать этот шаг дальше. Пусть y = gcd (b, c / x)

a*b/c = (a/x) * (b/y) * y 
        ------------------
        ((c/x)/y) * y 

a*b/c = (a/x) * (b/y) 
        ------------
           (c/(xy))

Вот код для получения gcd.

static long gcd(long a, long b) 
{ 
  if (b == 0) 
    return a; 
  return gcd(b, a % b);  
} 

Answer 5

Вы предполагаете следующее:

long a,b,c;
long result = a*b/c;

• Все 3 операнда имеют тип long
• Результат типа long
• a * b может быть больше и не соответствовать типу long

Математически говоря:

(a * b) / c = (a / c) * b = a * (b / c)

• кондиционер, безусловно, имеет тип long
• b / c, безусловно, относится к типу long

Пока ваше предположение верно (результат имеет тип long), вам нужно разделить большее из (a) и (b) на (c) и затем выполнить умножение, чтобы получить результат, который не больше тип long.

Но:

Тип long не содержит десятичных дробей. Поэтому нам нужно сохранить и остаток от деления.

(a * b) / c = (a / c) * b + (a % c) * b

Мы предполагаем, что (a% c) * b дает нам явное длинное значение, а не двойное значение. В качестве альтернативы мы можем использовать:

(a * b) / c = (b / c) * a + (b % c) * a

Мы предполагаем, что (b% c) * a не содержит десятичных дробей.

Тем не менее @Jesper прав. Пока вы не планируете делать это вычисление несколько миллионов раз, вам будет хорошо с существующими большими типами.