Самый безопасный и эффективный способ вычисления целочисленной операции, которая может переполняться

Предположим, что у нас есть 2 константы A и B и переменная i, все 64-битные целые числа. И мы хотим вычислить простую общую арифметическую операцию, такую ​​как:

i * A / B    (1)

Чтобы упростить задачу, допустим, что переменная i всегда находится в диапазоне [INT64_MIN*B/A, INT64_MAX*B/A], так что конечный результат арифметической операции (1) не переполняется (т.е. соответствует в диапазоне [INT64_MIN, INT64_MAX]).

Кроме того, i считается более вероятным в дружественном диапазоне Range1 = [INT64_MIN/A, INT64_MAX/A] (то есть: близком к 0), однако i может быть (менее вероятно) снаружи этот диапазон. В первом случае тривиальное целочисленное вычисление i * A не будет переполняться (поэтому мы назвали диапазон дружественным); и в последнем случае тривиальное целочисленное вычисление i * A будет переполняться, что приведет к ошибочному результату при вычислении (1).

Каким будет "самый безопасный" и "самый эффективный" способ вычисления операции (1) (где "безопаснее" означает: сохранение точности или, по крайней мере, достойной точности и где "наиболее эффективным" означает: наименьшее среднее время вычислений), если i более вероятно в диапазоне дружественных Range1.

В настоящее время решение, реализованное в настоящее время в коде, является следующим:

(int64_t)((double)A / B * i)

какое решение является достаточно безопасным (без переполнения), хотя и неточным (прецизионные потери из-за двойного значения 53-разрядного ограничения) и довольно быстро, потому что двойное деление (double)A / B предварительно вычисляется во время компиляции, позволяя вычислять только двойное умножение во время выполнения.

Ответы

Ответ 1

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

Контрольный показатель измеряет время вычисления различных реализаций, когда i находится внутри дружественного диапазона Range1= [INT64_MIN/A, INT64_MAX/A], а когда i находится за пределами дружественного диапазона (еще в безопасном диапазоне Range2= [INT64_MIN*B/A, INT64_MAX*B/A]).

Каждая реализация выполняет "безопасное" (т.е. без какого-либо переполнения) вычисления операции: i * A / B (за исключение 1-го осуществления, учитывая, как эталонное время вычислений). Однако некоторые реализации могут возвращать нечастый неточный результат вычисления (какое поведение уведомлено).

Некоторые предлагаемые решения не были протестированы или не перечислены ниже; это: решение с использованием __int128 (неподдерживается компилятором ms vc), но вместо этого используется int128_t; решения с использованием расширенных 80 бит long double (неподдерживаемый компилятором ms vc); решение с использованием InfInt (работает и проверено, хотя слишком медленно, чтобы стать достойным конкурентом).

Измерения времени указаны в ps/op (пикосекунды за операцию). Базовая платформа - это Intel Q6600 @3GHz под Windows 7 x64, исполняемый файл скомпилирован с MS vc14, x64/Release target. Переменные, константы и функции, указанные в дальнейшем, определяются как:

int64_t       i;
const int64_t A     = 1234567891;
const int64_t B     = 4321987;
inline bool   in_safe_range(int64_t i) { return (INT64_MIN/A <= i) && (i <= INT64_MAX/A); }
  • (i * A / B) [ссылка]
    i в Range1: 1469 ps/op, i вне Range1: нерелевантный (переполнение)
  • ((int64_t)((double)i * A / B))
    i в Range1: 10613 ps/op, i вне Range1: 10606 ps/op
    Примечание: нечастый неточный результат (максимальная ошибка = 1 бит) во всем диапазоне Range2
  • ((int64_t)((double)A / B * i))
    i в Range1: 1073 ps/op, i вне Range1: 1071 ps/op
    Примечание: нечастый неточный результат (максимальная ошибка = 1 бит) во всем диапазоне Range2
    Примечание: компилятор, вероятно, предварительно вычислил (double)A / B, что привело к наблюдаемому повышению производительности по сравнению с предыдущим решением.
  • (!in_safe_range(i) ? (int64_t)((double)A / B * i) : (i * A / B))
    i в Range1: 2009 ps/op, i вне Range1: 1606 ps/op
    Примечание: редкий неточный результат (максимальная ошибка = 1 бит) за пределами диапазона1
  • ((int64_t)((int128_t)i * A / B)) [boost int128_t]
    i в Range1: 89924 ps/op, i вне Range1: 89289 ps/op
    Примечание: форматирование int128_t сильно сказывается на платформе сканера (не знаю, почему)
  • ((i / B) * A + ((i % B) * A) / B)
    i в Range1: 5876 ps/op, i вне Range1: 5879 ps/op
  • (!in_safe_range(i) ? ((i / B) * A + ((i % B) * A) / B) : (i * A / B))
    i в Range1: 1999 ps/op, i вне Range1: 6135 ps/op

Заключение
a) Если небольшие ошибки вычислений приемлемы во всем диапазоне Range2, то решение (3) является самым быстрым, даже быстрее, чем вычисление прямого целого, указанное в качестве ссылки. < ш > b) Если ошибки вычисления неприемлемы в дружественном диапазоне Range1, но приемлемо вне этого диапазона, то решение (4) является самым быстрым. c) Если ошибки вычисления неприемлемы во всем диапазоне Range2, то решение (7) выполняет также решение (4) в дружественном диапазоне Range1 и остается прилично быстрой вне этого диапазона.

Ответ 2

Если вы не можете получить более высокие оценки на диапазонах, то лучше всего следовать советам iammilind, чтобы использовать __int128.

Причина в том, что в противном случае вам нужно было бы реализовать полную логику слова для умножения двойного слова и двойного слова путем разделения слов. Руководства для процессоров Intel и AMD содержат полезную информацию и готовый код, но он довольно активно участвует, а использование C/С++ вместо ассемблера делает вещи вдвойне сложными.

Все хорошие компиляторы раскрывают полезные примитивы как внутренние. Список Microsoft, похоже, не содержит примитив, подобный muldiv, но __mul128 intrinsic дает две половинки 128-битного продукта в виде двух 64-битных целых чисел. Исходя из этого, вы можете выполнить длинное деление двух цифр на одну цифру, где одна цифра будет 64-битным целым числом (обычно называемым "конечность", потому что больше, чем цифра, но все еще только часть целого). Все еще довольно активно, но намного лучше, чем использование чистого C/С++. Однако переносимость - это не лучше, чем использование __int128 напрямую. По крайней мере, так, что разработчики компилятора уже сделали для вас всю тяжелую работу.

Если ваш домен приложения может дать вам полезные оценки, например, (u % d) * v не будет переполняться, вы можете использовать идентификатор

(u * v) / d = (u / d) * v + ((u % d) * v) / d

где / означает целочисленное деление, если u неотрицательно и d положительно (в противном случае вы можете столкнуться с свободой, допустимой для семантики оператора %).

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

Кроме того, с неподписанными типами вы можете отказаться от таких правил, как s = a (+) b (где (+) возможно переполненное беззнаковое дополнение), у вас будет либо s == a + b, либо s < a && s < b, что позволяет обнаруживать переполнение после факт с дешевыми операциями.

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

Ответ 3

Я думаю, вы можете обнаружить переполнение до того, как это произойдет. В вашем случае i * A / B вас беспокоит только часть i * A, потому что разделение не может переполняться.

Вы можете обнаружить переполнение, выполнив проверку bool overflow = i > INT64_MAX / A. Вам нужно будет изменить это в зависимости от знака операндов и результата.

Ответ 4

Некоторые реализации позволяют __int128_t. Проверьте, позволяет ли ваша реализация, чтобы вы могли использовать его в качестве заполнителя вместо double. См. Ниже сообщение:
Почему нет int128_t?

Если вас не очень беспокоит "быстрая", то для хорошей переносимости я бы предложил использовать только заголовки только библиотеки С++ "InfInt" .

Довольно просто использовать библиотеку. Просто создайте экземпляр класса InfInt и начните его использовать:

InfInt myint1 = "15432154865413186646848435184100510168404641560358"; 
InfInt myint2 = 156341300544608LL;

myint1 *= --myint2 - 3;
std::cout << myint1 << std::endl;

Ответ 5

Не уверен в значениях границ, будет (i / B) * A + (i % B) * A / B help?