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