Арифметика с насыщением - это версия арифметики, в которой все операции, такие как сложение и умножение, ограничены в фиксированный диапазон между минимальным и максимальным значением.
Если результат операции больше максимального, он устанавливается ("зафиксирован ") на максимум; если он ниже минимума, он ограничивается минимумом. Название происходит от того, как значение становится «насыщенным», когда достигает крайних значений; дальнейшее прибавление к максимуму или вычитание из минимума не повлияет на результат.
Например, если допустимый диапазон значений составляет от -100 до 100, следующие арифметические операции с насыщением дают следующие значения:
Как видно из этих примеров, знакомые свойства, такие как ассоциативность и распределенность, могут не работать в арифметике насыщения. Это затрудняет работу с абстрактной математикой, но она играет важную роль в цифровом оборудовании и алгоритмах, где значения имеют максимальные и минимальные представимые диапазоны.
Обычно универсальное микропроцессоры не реализуют целочисленные арифметические операции с использованием арифметики насыщения; вместо этого они используют более простую в реализации модульную арифметику, в которой значения, превышающие максимальное значение «, оборачиваются вокруг » до минимального значения, как часы на часах, переходящие с 12 на 1. В аппаратном обеспечении модульная арифметика с минимумом нуля и максимумом r - 1, где r - основание, может быть реализована простым отбрасыванием всех, кроме младших n цифр. Для двоичного оборудования, которым является подавляющее большинство современного оборудования, основание системы счисления равно 2, а цифры - биты.
Однако, хотя арифметика с насыщением более сложна в реализации, она имеет множество практических преимуществ. Результат максимально приближен к истинному ответу; для 8-битной двоичной арифметики со знаком, когда правильный ответ равен 130, значительно менее удивительно получить ответ 127 из арифметики с насыщением, чем получить ответ -126 из модульной арифметики. Аналогично, для 8-битной двоичной беззнаковой арифметики, когда правильный ответ равен 258, менее удивительно получить ответ 255 от насыщающей арифметики, чем получить ответ 2 от модульной арифметики.
Арифметика насыщения также позволяет последовательно обнаруживать переполнение сложений и умножений без бита переполнения или чрезмерных вычислений путем простого сравнения с максимальным или минимальным значением (при условии, что данные не могут принимать эти значения).
Кроме того, арифметика насыщения позволяет использовать эффективные алгоритмы для решения многих задач, особенно в цифровой обработке сигналов. Например, регулировка уровня громкости звукового сигнала может привести к переполнению, а насыщенность вызывает значительно меньшие искажения звука, чем циклический. По словам исследователей Г. А. Константинидеса и др. :
При сложении двух чисел с использованием представления дополнения до двух, переполнение приводит к феномену «циклического перехода». Результатом может быть катастрофическая потеря отношения сигнал / шум в системе DSP. Поэтому сигналы в схемах DSP обычно либо масштабируются соответствующим образом, чтобы избежать переполнения для всех входных векторов, кроме самых крайних, либо создаются с использованием арифметических компонентов насыщения.
Арифметические операции с насыщением доступны на многих современных платформах, и в частности, было одно из расширений, сделанных платформой Intel MMX специально для таких приложений обработки сигналов. Эта функциональность также доступна в более широких версиях в целочисленных наборах команд SSE2 и AVX2.
Арифметика насыщения для целых чисел также реализована в программном обеспечении для ряда языков программирования, включая C, C ++, например GNU Compiler Collection, LLVM IR и Eiffel. Это помогает программистам лучше предвидеть и понимать последствия переполнения, а в случае компиляторов обычно выбирают оптимальное решение.
Насыщение сложно реализовать эффективно в программном обеспечении на машине с использованием только модульных арифметических операций, поскольку простые реализации требуют ветвей, которые создают огромные задержки конвейера. Однако можно реализовать сложение и вычитание с насыщением в программном обеспечении без ветвей, используя только модульные арифметические и поразрядные логические операции, которые доступны на всех современных процессорах и их предшественниках, включая все процессоры x86 (назад к исходным Intel 8086 ) и некоторые популярные 8-битные процессоры (некоторые из которых, например, Zilog Z80, все еще находятся в производстве). С другой стороны, на простых 8-битных и 16-битных процессорах алгоритм ветвления может быть быстрее, если он запрограммирован в сборке, поскольку нет конвейеров, которые можно было бы остановить, и каждая инструкция всегда занимает несколько тактовых циклов. На x86, который предоставляет флаги переполнения и условные перемещения, возможен очень простой код без ветвлений.
Хотя арифметика насыщения менее популярна для целочисленной арифметики на оборудовании, IEEE Стандарт с плавающей запятой, наиболее популярная абстракция для работы с приблизительными действительными числами, использует форму насыщения, при которой переполнение преобразуется в «бесконечность» или «отрицательную бесконечность», и любая другая операция над этим результатом продолжает приводить к такое же значение. Это имеет то преимущество перед простым насыщением, что последующие операции по уменьшению значения не приведут к ошибочно "разумному" результату, например, в вычислении . В качестве альтернативы могут быть особые состояния, такие как «переполнение экспоненты» (и «истощение показателя»), которые аналогичным образом сохранятся при последующих операциях, или вызовут немедленное завершение, или будут проверяться на предмет, как в IF ACCUMULATOR OVERFLOW...
как в FORTRAN для IBM704 (октябрь 1956 г.).