Обнаружение умножения переполнения целых чисел uint64_t с помощью C
Есть ли эффективный и переносимый способ проверки, когда операции умножения с переполнением операндов int64_t или uint64_t в C?
Например, для добавления uint64_t я могу сделать:
if (UINT64_MAX - a < b) overflow_detected();
else sum = a + b;
Но я не могу перейти к аналогичному простому выражению для умножения.
Все, что происходит со мной, это разбить операнды на высокие и низкие uint32_t части и выполнить умножение этих частей, проверяя переполнение, что-то действительно уродливое и, вероятно, неэффективное тоже.
Обновление 1: некоторый контрольный код, реализующий несколько подходов
Обновление 2: добавлен метод Йенса Густедта
программа сравнения:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define N 100000000
int d = 2;
#define POW_2_64 ((double)(1 << 31) * (double)(1 << 31) * 4)
#define calc_b (a + c)
// #define calc_b (a + d)
int main(int argc, char *argv[]) {
uint64_t a;
uint64_t c = 0;
int o = 0;
int opt;
if (argc != 2) exit(1);
opt = atoi(argv[1]);
switch (opt) {
case 1: /* faked check, just for timing */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
if (c > a) o++;
c += b * a;
}
break;
case 2: /* using division */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
if (b && (a > UINT64_MAX / b)) o++;
c += b * a;
}
break;
case 3: /* using floating point, unreliable */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
if ((double)UINT64_MAX < (double)a * (double)b) o++;
c += b * a;
}
break;
case 4: /* using floating point and division for difficult cases */
for (a = 0; a < N; a++) {
uint64_t b = a + c;
double m = (double)a * (double)b;
if ( ((double)(~(uint64_t)(0xffffffff)) < m ) &&
( (POW_2_64 < m) ||
( b &&
(a > UINT64_MAX / b) ) ) ) o++;
c += b * a;
}
break;
case 5: /* Jens Gustedt method */
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; }
if (b1 > 0xffffffff) o++;
else {
uint64_t a1l = (a1 & 0xffffffff) * b1;
uint64_t a1h = (a1 >> 32) * b1 + (a1l >> 32);
if (a1h >> 32) o++;
}
c += b1 * a1;
}
break;
default:
exit(2);
}
printf("c: %lu, o: %u\n", c, o);
}
До сих пор случай 4, который использует с плавающей точкой для фильтрации большинства случаев, является самым быстрым, когда предполагается, что переполнение очень необычно, по крайней мере, на моем компьютере, где он всего в два раза медленнее, чем случай без дела.
Случай 5, на 30% медленнее, чем 4, но он всегда выполняет то же самое, нет никаких номеров специальных случаев, которые требуют более медленной обработки, как это происходит с 4.
Ответы
Ответ 1
Если вы хотите избежать деления, как в ответе Амброза:
Сначала вы должны увидеть, что меньшее из двух чисел, например a, меньше 2 32 иначе результат все равно будет переполняться. Пусть b разбивается на два 32-битных слова, которые b= c 2 32 + 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);
}
так что это два умножения, два смены, некоторые дополнения и проверки условий. Это может быть более эффективным, чем деление, потому что, например, два умножения могут быть конвейерными в параллельном режиме. Вам нужно будет проверить, что лучше для вас.
Ответ 2
Собственно, для умножения можно использовать тот же принцип:
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;
Для целых чисел со знаком можно сделать, вам, вероятно, понадобится случай для каждой комбинации знаков.
Ответ 3
Связанный вопрос с некоторыми (надеюсь) полезными ответами: Лучший способ обнаружения переполнения целых чисел в C/С++. Кроме того, он не охватывает только uint64_t;)
Ответ 4
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". Стандарт говорит, что unsigned itegers не могут переполняться. Глава 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.
Ответ 5
Он может не обнаруживать точные переполнения, но в общем случае вы можете проверить результат умножения в логарифмическом масштабе:
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, иначе это очень портативный и удобный способ проверки умножений больших чисел.
