Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Арифметика с насыщением - это версия арифметики, в которой все операции, такие как сложение и умножение, ограничены фиксированным диапазоном между минимальным и максимальным значением.

Если результат операции больше максимального, он устанавливается (« фиксируется ») на максимум; если он ниже минимума, он ограничивается минимумом. Название происходит от того, как значение становится «насыщенным», когда достигает крайних значений; дальнейшее прибавление к максимуму или вычитание из минимума не повлияет на результат.

Например, если допустимый диапазон значений составляет от -100 до 100, следующие арифметические операции с насыщением производят следующие значения:

  • 60 + 30 → 90.
  • 60 + 43 → 100 ( не ожидалось 103.)
  • (60 + 43) - (75 + 75) → 0. ( не ожидаемый −47.) (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.)

Как видно из этих примеров, знакомые свойства, такие как ассоциативность и распределенность, могут не соответствовать арифметике насыщения. [1] С этим неприятно работать в абстрактной математике, но он играет важную роль в цифровом оборудовании и алгоритмах, где значения имеют максимальные и минимальные представимые диапазоны.

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

Обычно микропроцессоры общего назначения не реализуют целочисленные арифметические операции с использованием арифметики насыщения; вместо этого, они используют проще в реализации модульной арифметики , в которой значение , превышающее значение максимального « обернуть вокруг » до минимального значения, как часы на часы , проходящих от 12 до 1. В аппаратных средств, модульная арифметике с минимумом ноль и максимум r n - 1, где r - основание системы счисления, может быть реализовано простым отбрасыванием всех цифр, кроме младших n . Для двоичного оборудования, которым является подавляющее большинство современного оборудования, основание системы счисления равно 2, а цифры - биты.

Однако, хотя арифметика с насыщением более сложна в реализации, она имеет множество практических преимуществ. Результат максимально приближен к истинному ответу; для 8-битной двоичной арифметики со знаком, когда правильный ответ равен 130, гораздо менее удивительно получить ответ 127 из арифметики с насыщением, чем получить ответ -126 из модульной арифметики. Точно так же для 8-битной двоичной арифметики без знака, когда правильный ответ равен 258, менее удивительно получить ответ 255 от насыщающей арифметики, чем получить ответ 2 от модульной арифметики.

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

Кроме того, арифметика насыщения позволяет использовать эффективные алгоритмы для решения многих задач, особенно при цифровой обработке сигналов . Например, регулировка уровня громкости звукового сигнала может привести к переполнению, а насыщенность вызывает значительно меньшие искажения звука, чем циклический. По словам исследователей Г.А. Константинидеса и др .: [2]

При добавлении двух чисел с использованием представления дополнения до двух, переполнение приводит к явлению «циклического перехода». Результатом может быть катастрофическая потеря отношения сигнал / шум в системе DSP. Поэтому сигналы в схемах DSP обычно либо масштабируются соответствующим образом, чтобы избежать переполнения для всех входных векторов, кроме самых крайних, либо генерируются с использованием арифметических компонентов насыщения.

Реализации [ править ]

Арифметические операции с насыщением доступны на многих современных платформах и, в частности, были одним из расширений платформы Intel MMX специально для таких приложений обработки сигналов. Эта функциональность также доступна в более широких версиях целочисленных команд SSE2 и AVX2 .

Арифметика насыщения для целых чисел также была реализована в программном обеспечении для ряда языков программирования, включая C , C ++ , таких как GNU Compiler Collection , [3] LLVM IR и Eiffel . Это помогает программистам лучше предвидеть и понимать последствия переполнения, а в случае компиляторов обычно выбирают оптимальное решение.

Насыщение сложно реализовать эффективно в программном обеспечении на машине, использующей только модульные арифметические операции, поскольку для простых реализаций требуются ветви, которые создают огромные задержки в конвейере. Однако можно реализовать сложение и вычитание с насыщением в программном обеспечении без ветвей , используя только модульные арифметические и побитовые логические операции, которые доступны на всех современных процессорах и их предшественниках, включая все процессоры x86 (назад к исходному Intel 8086 ) и некоторые популярные 8-битные процессоры (некоторые из которых, например Zilog Z80, все еще в производстве). С другой стороны, на простых 8-битных и 16-битных процессорах алгоритм ветвления может быть быстрее, если он запрограммирован на сборке, поскольку нет конвейеров, которые можно было бы остановить, и каждая инструкция всегда занимает несколько тактовых циклов. На x86, который предоставляет флаги переполнения и условные перемещения , возможен очень простой код без ветвлений. [4]

Хотя арифметика насыщения менее популярна для целочисленной арифметики на оборудовании, стандарт с плавающей запятой IEEE , наиболее популярная абстракция для работы с приблизительными действительными числами, использует форму насыщения, при которой переполнение преобразуется в «бесконечность» или «отрицательную бесконечность», и любая другая операция над этим результатом продолжает давать то же значение. Это имеет преимущество перед простым насыщением в том, что последующие операции по уменьшению значения не приведут к ошибочно «разумному» результату, например, при вычислении . В качестве альтернативы, могут быть особые состояния, такие как «переполнение экспоненты» (и «истощение показателя»), которые аналогичным образом сохранятся при последующих операциях или вызовут немедленное завершение, или будут проверяться на предмет, как вIF ACCUMULATOR OVERFLOW ... как в FORTRAN для IBM704 (октябрь 1956 г.).

См. Также [ править ]

Заметки [ править ]

  1. ^ Фактически,арифметика без насыщения также может страдать от сбоев ассоциативности и распределенности в средах с ограниченной точностью, но такие сбои, как правило, менее очевидны.
  2. ^ GA Constantinides, PYK Cheung и W. Luk. Синтез арифметических архитектур насыщения .
  3. ^ "GNU Compiler Collection (GCC) Internals: Arithmetic" . Документация GCC . Встроенные функции на стороне языка
  4. ^ "Безводная насыщающая арифметика" . locklessinc.com . Архивировано из оригинала на 2019-02-13. CS1 maint: discouraged parameter (link)

Внешние ссылки [ править ]

  • САРИТ: Безопасная арифметика - отчет о проделанной работе : отчет об арифметическом компоненте насыщения для Eiffel .
  • saturating , библиотека C ++ только для заголовков для насыщения ариметики с точки зрения встроенных функций GCC Overflow.