Как определить заранее, может ли расчет без знака переполниться?

Question

Как личный проект, я работаю над реализацией типа числа Arbitrary Precision для моего любимого проекта.

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

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

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

Например: Multiplying two 64 bit Integers if each are large enough will cause an overflow. Я хочу обнаружить это и преобразовать числа в мой тип чисел, только если результат может превышает разрешение 64 бита.В этом эксперименте я буду работать с знаковыми числами.

Какой самый разумный и эффективный способ обнаружения переполнения / недостаточного заполнения?

Answer 1

Об этом есть бумага Джона Регера .

Answer 2

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

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

Это может иметь смысл только для больших типов данных, для которых оператор является дорогостоящим, дляпростые вещи (даже для 64-битных чисел), я думаю, что вы можете положиться на встроенную арифметику процессора .. см. этот вопрос: неопределенное поведение при превышении 64 бит

Answer 3

Почти всегда проще (и часто быстрее) выполнять наивные вычисления и обнаруживать переполнение.Есть ли конкретная причина, по которой вы хотели бы обнаружить возможность перед выполнением вычислений?

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

Вот (очень) простой пример: если я добавлю два 64-разрядных числа без знака, я могу проверить переполнение, сравнив сумму слюбое из добавлений - если оно меньше, чем произошло переполнение.Таким образом, обнаружение переполнения после вычисления требует только одного сравнения (действительно очень дешевого).