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

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

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

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

Это называется методом Schrage, см., например. там.