Почему быстрее вычислять произведение последовательного массива целых чисел, выполняя вычисление попарно?

Ответ 1

BigInteger имеет быстрый регистр для чисел 31 бит или меньше. Когда вы выполняете парное умножение, это означает, что выполняется определенный быстрый путь, который умножает значения на один ulong и устанавливает значение более явно:

public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) {
  ...
  if (reg1._iuLast == 0) {
    if (reg2._iuLast == 0)
      Set((ulong)reg1._uSmall * reg2._uSmall);
    else {
      ...
    }
  }
  else if (reg2._iuLast == 0) {
    ...
  }
  else {
    ...
  }
}

public void Set(ulong uu) {
  uint uHi = NumericsHelpers.GetHi(uu);
  if (uHi == 0) {
    _uSmall = NumericsHelpers.GetLo(uu);
    _iuLast = 0;
  }
  else {
    SetSizeLazy(2);
    _rgu[0] = (uint)uu;
    _rgu[1] = uHi;
  }
  AssertValid(true);
}

100% прогнозируемая ветка, подобная этой, идеально подходит для JIT, и этот быстрый путь должен быть оптимизирован очень хорошо. Возможно, что _rgu[0] и _rgu[1] являются четными. Это очень дешево, поэтому эффективно сокращает количество реальных операций в два раза.

Так почему же группа из трех так медленнее? Очевидно, что он должен быть медленнее, чем для k = 2; у вас гораздо меньше оптимизированных умножений. Более интересным является то, почему он медленнее, чем k = 1. Это легко объясняется тем, что внешнее умножение total теперь попадает на медленный путь. Для k = 2 это влияние смягчается, уменьшая вдвое количество умножений и потенциальную вставку массива.

Однако эти факторы не помогают k = 3, и на самом деле медленный случай болит k = 3 намного больше. Второе умножение в случае k = 3 попадает в этот случай

  if (reg1._iuLast == 0) {
    ...
  }
  else if (reg2._iuLast == 0) {
    Load(ref reg1, 1);
    Mul(reg2._uSmall);
  }
  else {
    ...
  }

который выделяет

  EnsureWritable(1);

  uint uCarry = 0;
  for (int iu = 0; iu <= _iuLast; iu++)
    uCarry = MulCarry(ref _rgu[iu], u, uCarry);

  if (uCarry != 0) {
    SetSizeKeep(_iuLast + 2, 0);
    _rgu[_iuLast] = uCarry;
  }

почему это имеет значение? Ну, EnsureWritable(1) вызывает

uint[] rgu = new uint[_iuLast + 1 + cuExtra];

поэтому rgu становится длиной 3. Количество проходов в коде total определяется в

public void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2)

а

    for (int iu1 = 0; iu1 < cu1; iu1++) {
      ...
      for (int iu2 = 0; iu2 < cu2; iu2++, iuRes++)
        uCarry = AddMulCarry(ref _rgu[iuRes], uCur, rgu2[iu2], uCarry);
      ...
    }

что означает, что мы имеем в общей сложности операции len(total._rgu) * 3. Это ничего нам не спасло! Для k = 1 проходит только len(total._rgu) * 1 - мы просто делаем это три раза!

На внешнем цикле существует оптимизация, которая уменьшает это значение до len(total._rgu) * 2:

      uint uCur = rgu1[iu1];
      if (uCur == 0)
        continue;

Тем не менее, они "оптимизируют" эту оптимизацию таким образом, что больно гораздо больше, чем раньше:

if (reg1.CuNonZero <= reg2.CuNonZero) {
  rgu1 = reg1._rgu; cu1 = reg1._iuLast + 1;
  rgu2 = reg2._rgu; cu2 = reg2._iuLast + 1;
}
else {
  rgu1 = reg2._rgu; cu1 = reg2._iuLast + 1;
  rgu2 = reg1._rgu; cu2 = reg1._iuLast + 1;
}

Для k = 2, который заставляет внешний цикл превышать total, так как reg2 не содержит нулевых значений с высокой вероятностью. Это здорово, потому что total способ длиннее partialTotal, поэтому чем меньше проходит, тем лучше. Для k = 3 EnsureWritable(1) всегда будет создавать запасное пространство, потому что умножение трех чисел длиной не более 15 бит никогда не может превышать 64 бит. Это означает, что хотя мы все еще делаем только один проход total для k = 2, мы делаем два для k = 3!

Это начинает объяснять, почему скорость снова увеличивается за пределами k = 3: количество проходов на добавление увеличивается медленнее, чем количество добавлений уменьшается, так как вы добавляете только 15 бит к внутреннему значению каждый раз. Внутренние умножения быстрые относительно массивных умножений total, поэтому чем больше времени потрачено на консолидацию значений, тем больше времени сохраняется в проходах над total. Кроме того, оптимизация реже пессимистична.

Он также объясняет, почему нечетные значения занимают больше времени: они добавляют дополнительное 32-разрядное целое к массиву _rgu. Это произойдет не так чисто, если ~ 15 бит не были настолько близки к половине 32.

Стоит отметить, что есть много способов улучшить этот код; комментарии здесь о том, почему, а не как это исправить. Самое простое улучшение - это забивать значения в куче и умножать только два наименьших значения за раз.

Ответ 2

Время, необходимое для умножения BigInteger, зависит от размера продукта.

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

Вы можете сделать еще лучше, если вы всегда умножаете два наименьших фактора (исходные факторы или промежуточные продукты), которые еще предстоит умножить, пока вы не дойдете до полного продукта.

Ответ 3

Я думаю, что у вас есть ошибка ('+' вместо '*').

partialTotal * = я + j;

Хорошо проверить, что вы получаете правильный ответ, а не только интересные показатели производительности.

Но мне любопытно, что побудило вас попробовать это. Если вы найдете разницу, я бы ожидал, что это будет связано с оптимальностью в распределении регистров и/или памяти. И я ожидаю, что это будет 0-30% или что-то в этом роде, а не 50%.