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

В качестве личного проекта я работаю над реализацией типа чисел произвольной точности для моего любимого проекта.

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

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

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

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

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


c math arbitrary-precision
person Community    schedule 08.11.2011    source источник
comment
Никогда не пробовал подобный проект, поэтому остались только вопросы: какой смысл заранее знать о переполнении? Оптимизация для меньших чисел, чтобы быть быстрой, или что-то менее очевидное? Вам нужно точное решение или принять решение, которое может привести к ложному срабатыванию сигнализации переполнения?   -  person vmatyi    schedule 09.11.2011
comment
Ваш вопрос и ваш комментарий в ответ на один из ответов говорят, что вы используете подписанные операнды, но в заголовке написано без знака. Что он? С беззнаковой арифметикой, вероятно, проще иметь дело, и, вероятно, она больше подходит для работы с числами произвольной точности.   -  person Keith Thompson    schedule 09.11.2011
comment
Я буду выполнять знаковые произвольные вычисления, используя беззнаковые примитивные типы в качестве базовых компонентов, как в массиве беззнаковых 64-битных длин, которые представляют базу   -  person    schedule 09.11.2011

Ответы (3)


arrow_upward
2
arrow_downward

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

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

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

person Karoly Horvath    schedule 08.11.2011
comment
Потому что так вы можете вызвать переполнение. Если это действительно происходит, это означает, что одно из ваших чисел уже большое. - person Xavier Ho; 09.11.2011

arrow_upward
2
arrow_downward

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

person Dan Kruchinin    schedule 08.11.2011

arrow_upward
0
arrow_downward

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

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

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

person Stephen Canon    schedule 08.11.2011
comment
Ваш пример верен только в случае беззнаковых операндов, в общем случае он не работает. - person Oliver Charlesworth; 09.11.2011
comment
И поведение подписанного переполнения не определено. - person Keith Thompson; 09.11.2011
comment
@Keith: Конечно, для примитивных типов. ОП говорит о реализации типа произвольной точности. Он должен иметь возможность обрабатывать переполнение, чтобы расширить представление (и, таким образом, предотвратить переполнение!). - person Oliver Charlesworth; 09.11.2011
comment
@OliCharlesworth: я думаю, он спрашивал о переполнении в примитивных типах, используемых в реализации. Например, если массив 64-битных чисел представляет 6400-битное число, я предполагаю, что он спрашивал о 64-битном переполнении. Джаррод, можешь пояснить? - person Keith Thompson; 09.11.2011
comment
Как только вы примете во внимание недостаточный расход, этот метод больше не работает. =| - person Xavier Ho; 09.11.2011
comment
@OliCharlesworth: Следует отметить две вещи: во-первых, при работе с числами произвольной точности обычно отдельно сохраняются беззнаковая величина и знак. Таким образом, вам обычно нужно иметь возможность обнаруживать только неподписанные переполнения. Во-вторых, что более важно, процессор обнаруживает переполнение/недополнение со знаком так же легко, как и переполнение без знака. Не существует удобного портативного способа получить установленные флаги, но это возможно сделать на любой разумной платформе — это правильный подход к этой задаче. - person Stephen Canon; 09.11.2011