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