обнаружение умножения переполнения целых чисел uint64_t на C

Если вы хотите избежать разделения, как в ответе Амброза:

Сначала вы должны увидеть, что меньшее из двух чисел, скажем a, меньше 2 ³², иначе результат все равно будет переполнен. Пусть b разложится на два 32-битных слова: b = c 2 ³² + d.

Я считаю, что вычисление не так уж и сложно:

uint64_t mult_with_overflow_check(uint64_t a, uint64_t b) {
  if (a > b) return mult_with_overflow_check(b, a);
  if (a > UINT32_MAX) overflow();
  uint32_t c = b >> 32;
  uint32_t d = UINT32_MAX & b;
  uint64_t r = a * c;
  uint64_t s = a * d;
  if (r > UINT32_MAX) overflow();
  r <<= 32;
  return addition_with_overflow_check(s, r);
}

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

Собственно, тот же принцип можно использовать и для умножения:

uint64_t a;
uint64_t b;
...
if (b != 0 && a > UINT64_MAX / b) { // if you multiply by b, you get: a * b > UINT64_MAX
    < error >
}
uint64_t c = a * b;

Для целых чисел со знаком можно сделать то же самое, вам, вероятно, понадобится регистр для каждой комбинации знаков.

Связанный вопрос с некоторыми (надеюсь) полезными ответами: Лучший способ обнаружить целочисленное переполнение в C / C ++. Плюс это не распространяется только на uint64_t;)

case 6:
    for (a = 0; a < N; a++) {
        uint64_t b = a + c;
        uint64_t a1, b1;
        if (a > b) { a1 = a; b1 = b; }
        else       { a1 = b; b1 = a; }
        uint64_t cc = b1 * a1;
        c += cc;
        if (b1 > 0xffffffff) o++;
        else {
            uint64_t a1l = (a1 & 0xffffffff) + (a1 >> 32);
            a1l = (a1 + (a1 >> 32)) & 0xffffffff;
            uint64_t ab1l = a1l * b1;
            ab1l = (ab1l & 0xffffffff) + (ab1l >> 32);
            ab1l += (ab1l >> 32);
            uint64_t ccl = (cc & 0xffffffff) + (cc >> 32);
            ccl += (ccl >> 32);
            uint32_t ab32 = ab1l; if (ab32 == 0xffffffff) ab32 = 0;
            uint32_t cc32 = ccl; if (cc32 == 0xffffffff) cc32 = 0;
            if (ab32 != cc32) o++;
        }
    }
    break;

Этот метод сравнивает (возможно, переполнение) результат обычного умножения с результатом умножения, который не может быть переполнен. Все вычисления производятся по модулю (2 ^ 32 - 1).

Он сложнее и (скорее всего) не быстрее, чем метод Йенса Густедта.

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

Ответы на некоторые вопросы

Прежде всего о "your code is not portable". Да, код не переносится, потому что он использует uint64_t, который запрашивается в исходном вопросе. Строго говоря, вы не можете получить переносимый ответ с (u)int64_t, потому что это не требуется по стандарту.

О "once some overflow happens, you can not assume the result value to be anything". Стандарт говорит, что итераторы без знака не могут переполняться. Глава 6.2.5, пункт 9:

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

Таким образом, беззнаковое 64-битное умножение выполняется по модулю 2 ^ 64 без переполнения.

Теперь о "logic behind". «Хеш-функция» здесь не совсем правильное слово. Я использую только вычисления по модулю (2^32 - 1). Результат умножения может быть представлен как n*2^64 + m, где m - видимый результат, а n означает, насколько мы переполняемся. Начиная с 2^64 = 1 (mod 2^32 - 1), мы можем вычислить [true value] - [visible value] = (n*2^64 + m) - m = n*2^64 = n (mod 2^32 - 1). Если вычисленное значение n не равно нулю, происходит переполнение. Если он равен нулю, переполнения нет. Любые коллизии возможны только после n >= 2^32 - 1. Этого никогда не произойдет, поскольку мы проверяем, что одно из множителей меньше 2^32.

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

if (log(UINT64_MAX-1) - log(a) - log(b) < 0) overflow_detected(); // subtracting 1 to allow some tolerance when the numbers are converted to double
else prod = a * b;

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