Предотвращение переполнения при целочисленном умножении с последующим делением

Question

У меня есть две интегральные переменные a и b и константа s соотв.d.Мне нужно рассчитать значение (a*b)>>s соотв.a*b/d.Проблема в том, что умножение может переполниться, и окончательный результат не будет правильным, даже если a*b/d может соответствовать данному целочисленному типу.

Как это можно решить эффективно?Простое решение состоит в том, чтобы расширить переменную a или b до большего целочисленного типа, но не может быть большего целочисленного типа.Есть ли лучший способ решить проблему?

Answer 1

Если нет более крупного типа, вам нужно либо найти библиотеку стилей big-int, либо разобраться с ней вручную, используя длинное умножение.

Например, предположим, что a и b являются 16-битными. Затем вы можете переписать их как a = (1<<8)*aH + aL и b = (1<<8)*bH + bL (где все отдельные компоненты являются 8-битными числами). Тогда вы знаете, что общий результат будет:

(a*b) = (1<<16)*aH*bH
      + (1<<8)*aH*bL
      + (1<<8)*aL*bH
      + aL*bL

Каждый из этих 4 компонентов будет соответствовать 16-битному регистру. Теперь вы можете выполнить, например, сдвиг вправо на каждом из отдельных компонентов, будьте осторожны, чтобы правильно обращаться с переносками.

Answer 2

Если больший тип всего 64 бита, то прямое решение, скорее всего, приведет к эффективному коду. На процессорах x86 любое умножение двух 32-битных чисел приведет к переполнению в другом регистре. Поэтому, если ваш компилятор это понимает, он может сгенерировать эффективный код для Int64 result=(Int64)a*(Int64)b.

У меня была такая же проблема в C #, и компилятор сгенерировал довольно хороший код. А компиляторы C ++ обычно создают лучший код, чем .net JIT.

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

Answer 3

Я еще не проверил это полностью, но не могли бы вы сначала выполнить деление, а затем учесть оставшуюся часть за счет дополнительных операций? Поскольку d является степенью двойки, все деления могут быть сокращены до побитовых операций.

Например, всегда принимайте a > b (сначала нужно разделить большее число). Тогда a * b / d = ((a / d) * b) + (((a % d) * b) / d)

Answer 4

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

Это называется методом Шрейга, см., Например. есть .