aritmética de saturación

La aritmética de saturación es una versión de la aritmética en la que todas las operaciones, como la suma y la multiplicación , están limitadas a un rango fijo entre un valor mínimo y un valor máximo.

Si el resultado de una operación es mayor que el máximo, se fija (o se limita ) a ese valor; si es menor que el mínimo, se limita a ese valor. El nombre proviene de cómo el valor se "satura" una vez que alcanza los extremos; añadir valores al máximo o restar valores al mínimo no modificará el resultado.

Si el rango válido de valores es de -100 a 100, las siguientes operaciones aritméticas de saturación producen los siguientes valores:

• 60 + 30 → 90.
• 60 + 43 → 100. ( no el 103 esperado.)
• (60 + 43) − (75 + 25) → 0. ( no es el 3 esperado.) (103 − 100 → 0.)
• 10 × 11 → 100. ( no el esperado 110.)
• 99 × 99 → 100. ( no el 9801 esperado.)
• 30 × (5 − 1) → 100. ( no el esperado 120.) (30 × 4 → 100.)
• (30 × 5) − (30 × 1) → 70. ( no es el 120 esperado. no es el 100 anterior.) (100 − 30 → 70.)
• 30 - 100 - 100 → -100. ( no el esperado -170.)

Como se puede observar en estos ejemplos, propiedades familiares como la asociatividad y la distributividad pueden fallar en la aritmética de saturación. ^{[ a ]} ​​Esto hace que sea desagradable tratar con ella en matemáticas abstractas , pero tiene un papel importante que desempeñar en el hardware digital y los algoritmos donde solo se pueden representar valores que van desde un valor mínimo hasta un valor máximo.

Por lo general, los microprocesadores de propósito general no implementan operaciones aritméticas enteras mediante aritmética de saturación; en su lugar, utilizan la aritmética modular , más fácil de implementar, en la que los valores que superan el valor máximo se " redondean " al valor mínimo, como las horas en un reloj que pasan de las 12 a la 1. En hardware, la aritmética modular con un mínimo de cero y un máximo de r ⁿ − 1, donde r es la base , se puede implementar simplemente descartando todos los dígitos excepto los n más bajos . Para el hardware binario, que es la gran mayoría del hardware moderno, la base es 2 y los dígitos son bits.

Sin embargo, aunque más difícil de implementar, la aritmética de saturación presenta numerosas ventajas prácticas. El resultado es numéricamente lo más cercano posible a la respuesta correcta; para la aritmética binaria con signo de 8 bits, cuando la respuesta correcta es 130, es mucho menos sorprendente obtener una respuesta de 127 con la aritmética de saturación que obtener una respuesta de -126 con la aritmética modular. Del mismo modo, para la aritmética binaria sin signo de 8 bits, cuando la respuesta correcta es 258, es menos sorprendente obtener una respuesta de 255 con la aritmética de saturación que obtener una respuesta de 2 con la aritmética modular.

La aritmética de saturación también permite detectar de forma consistente el desbordamiento de sumas y multiplicaciones sin un bit de desbordamiento ni cálculos excesivos, mediante una simple comparación con el valor máximo o mínimo (siempre que el dato no pueda tomar estos valores).

Además, la aritmética de saturación permite algoritmos eficientes para muchos problemas, particularmente en el procesamiento de señales digitales . Por ejemplo, ajustar el nivel de volumen de una señal de sonido puede resultar en un desbordamiento, y la saturación causa una distorsión significativamente menor al sonido que el envolvimiento. En palabras de los investigadores GA Constantinides et al.: ^{[ 1 ]}

Al sumar dos números utilizando la representación en complemento a dos, el desbordamiento produce un fenómeno de "envolvimiento". Esto puede resultar en una pérdida catastrófica de la relación señal-ruido en un sistema DSP. Por lo tanto, en los diseños DSP, las señales generalmente se escalan adecuadamente para evitar el desbordamiento, excepto para los vectores de entrada más extremos, o se generan utilizando componentes aritméticos de saturación.

Las operaciones aritméticas de saturación están disponibles en muchas plataformas modernas, y en particular, fueron una de las extensiones desarrolladas por Intel MMX , específicamente para este tipo de aplicaciones de procesamiento de señales. Esta funcionalidad también está disponible en versiones más amplias en los conjuntos de instrucciones de enteros SSE2 y AVX2 . Asimismo, está disponible en el conjunto de instrucciones ARM NEON .

La aritmética de saturación para enteros también se ha implementado en software para varios lenguajes de programación, incluidos C y C++ , como la GNU Compiler Collection , ^{[ 2 ]} LLVM IR, Eiffel y Zig . El soporte para la aritmética de saturación se incluyó en la biblioteca estándar de C++ desde C++26 . Esto ayuda a los programadores a anticipar y comprender mejor los efectos del desbordamiento y, en el caso de los compiladores, a elegir la solución óptima.

La saturación es difícil de implementar de manera eficiente en software en una máquina con solo operaciones aritméticas modulares, ya que las implementaciones simples requieren bifurcaciones que crean enormes retrasos en la tubería. Sin embargo, es posible implementar suma y resta saturadas en software sin bifurcaciones , utilizando solo aritmética modular y operaciones lógicas bit a bit disponibles en todas las CPU modernas y sus predecesoras, incluidas todas las CPU x86 (desde el Intel 8086 original ) y algunas CPU populares de 8 bits (algunas de las cuales implementan el conjunto de instrucciones Z80 ) que aún están en producción. Por otro lado, en CPU simples de 8 y 16 bits, un algoritmo de bifurcación podría ser más rápido si se programa en lenguaje ensamblador, ya que no hay tuberías que se detengan y cada instrucción siempre toma varios ciclos de reloj. En x86, que proporciona indicadores de desbordamiento y movimientos condicionales , es posible un código sin bifurcaciones muy simple. ^{[ 3 ]}

Aunque la aritmética de saturación es menos popular para la aritmética de enteros en hardware, el estándar de punto flotante IEEE , la abstracción más popular para trabajar con números reales aproximados , utiliza una forma de saturación en la que el desbordamiento se convierte en "infinito" o "infinito negativo", y cualquier otra operación sobre este resultado continúa produciendo el mismo valor. Esto tiene la ventaja sobre la saturación simple de que las operaciones posteriores que disminuyen el valor no terminarán produciendo un resultado engañosamente "razonable", como en el cálculo.${\estilo de texto {\sqrt {x^{2}-y^{2}}}}$. Alternativamente, puede haber estados especiales como "desbordamiento de exponente" (y "subdesbordamiento de exponente") que persistirán de manera similar a través de operaciones posteriores, o causarán una terminación inmediata, o se comprobarán como IF ACCUMULATOR OVERFLOW ...en FORTRAN para el IBM 704 (octubre de 1956).

• Censura (estadísticas)

• SARITH: Aritmética segura – Informe de progreso : Informe sobre un componente de aritmética de saturación para Eiffel .
• saturating , una biblioteca C++ de solo encabezados para saturar aritmética en términos de funciones integradas de desbordamiento de GCC.