Введение

Тип арифметики, при которой выход ограничивается фиксированным диапазоном значений. Арифметика насыщения — это разновидность арифметики, в которой все операции, такие как сложение и умножение, ограничены фиксированным диапазоном между минимальным и максимальным значением. Если результат операции превышает максимальное значение, он устанавливается ("зажимается") на максимальное значение; если он ниже минимального значения, он зажимается на минимальное значение. Название происходит от того, как значение становится "насыщенным", достигнув предельных значений; дальнейшее увеличение максимума или уменьшение минимума не изменит результат. Например, если допустимый диапазон значений от −100 до 100, следующие операции с насыщением дают следующие значения: 60 + 30 → 90. 60 + 43 → 100. (а ожидалось 103.) (60 + 43) − (75 + 25) → 0. (а ожидалось 3.) (100 − 100 → 0.) 10 × 11 → 100. (а ожидалось 110.) 99 × 99 → 100. (а ожидалось 9801.) 30 × (5 − 1) → 100. (а ожидалось 120.) (30 × 4 → 100.) (30 × 5) − (30 × 1) → 70. (а ожидалось 120, а не предыдущие 100.) (100 − 30 → 70.) Вот еще один пример насыщающегося вычитания, когда допустимый диапазон от 0 до 100: 30 − 60 → 0. (а ожидалось 30.) Как видно из этих примеров, привычные свойства, такие как ассоциативность и дистрибутивность, могут не выполняться в арифметике насыщения. Это делает ее неудобной для работы в абстрактной математике, но она играет важную роль в цифровом оборудовании и алгоритмах, где значения имеют максимальный и минимальный представимые диапазоны.

Современное использование

Обычно, микропроцессоры общего назначения не реализуют операции целочисленной арифметики с использованием арифметики насыщения; вместо этого они используют более простую в реализации модульную арифметику, в которой значения, превышающие максимальное, "переполняются" к минимальному, подобно тому, как часы, переходя от 12 к 1. В аппаратном обеспечении модульную арифметику с минимумом, равным нулю, и максимумом, равным rn − 1, где r – основание системы счисления, можно реализовать, просто отбрасывая все, кроме младших n разрядов. Для двоичного оборудования, которым является подавляющее большинство современных систем, основание равно 2, а разряды – биты. Однако, несмотря на большую сложность реализации, арифметика насыщения обладает многочисленными практическими преимуществами. Результат максимально приближен к правильному ответу; для 8-битной двоичной знаковой арифметики, если правильный ответ равен 130, гораздо менее удивительно получить 127 при использовании арифметики насыщения, чем получить −126 при использовании модульной арифметики. Аналогично, для 8-битной двоичной беззнаковой арифметики, если правильный ответ равен 258, менее удивительно получить 255 при использовании арифметики насыщения, чем получить 2 при использовании модульной арифметики. Арифметика насыщения также позволяет последовательно обнаруживать переполнение при сложении и умножении без использования бита переполнения или избыточных вычислений, путем простого сравнения с максимальным или минимальным значением (при условии, что данные не могут принимать эти значения). Кроме того, арифметика насыщения позволяет создавать эффективные алгоритмы для решения многих задач, особенно в области цифровой обработки сигналов. Например, регулировка уровня громкости звукового сигнала может привести к переполнению, и насыщение вызывает значительно меньше искажений звука, чем переполнение по модулю. Как отмечают исследователи Г. А. Константинидес и др.:

Реализация

Арифметические операции насыщения доступны на многих современных платформах, и в частности, являлись одним из расширений, реализованных платформой Intel MMX, специально для приложений обработки сигналов. Эта функциональность также доступна в более широких версиях в наборах инструкций SSE2 и AVX2. Она также доступна в наборе инструкций ARM NEON. Арифметика насыщения для целых чисел также была реализована программно для ряда языков программирования, включая C, C++, таких как GNU Compiler Collection, LLVM IR и Eiffel. Это помогает программистам лучше предвидеть и понимать последствия переполнения, а в случае с компиляторами обычно позволяет выбрать оптимальное решение. Насыщение сложно эффективно реализовать программно на машине, оперирующей только модульной арифметикой, поскольку простые реализации требуют ветвлений, создающих значительные задержки в конвейере. Однако, возможно реализовать насыщающее сложение и вычитание программно без ветвлений, используя только модульную арифметику и побитовые логические операции, доступные на всех современных процессорах и их предшественниках, включая все процессоры x86 (вплоть до оригинального Intel 8086) и некоторые популярные 8-битные процессоры (некоторые из которых, такие как Zilog Z80, до сих пор находятся в производстве). С другой стороны, на простых 8-битных и 16-битных процессорах алгоритм с ветвлениями может оказаться быстрее, если он запрограммирован на ассемблере, поскольку там нет конвейеров, которые можно было бы остановить, и каждая инструкция всегда занимает несколько тактов. На x86, который предоставляет флаги переполнения и условные перемещения, возможен очень простой код без ветвлений. Хотя арифметика насыщения менее популярна для целочисленной арифметики в аппаратной части, стандарт IEEE для чисел с плавающей точкой, наиболее распространенная абстракция для работы с приближенными вещественными числами, использует форму насыщения, при которой переполнение преобразуется в "бесконечность" или "отрицательную бесконечность", и любая последующая операция над этим результатом продолжает давать то же значение. Это имеет преимущество перед простым насыщением в том, что последующие операции, уменьшающие значение, не приведут к получению ложно "разумного" результата, например, при вычислении. В качестве альтернативы могут существовать специальные состояния, такие как "переполнение экспоненты" (и "потери экспоненты"), которые также будут сохраняться в последующих операциях или вызывать немедленное завершение, либо проверяться, как в конструкции IF ACCUMULATOR OVERFLOW, как в FORTRAN для IBM704 (октябрь 1956 года).