Arithmétique saturée

Supposons une fonction de cadrage

[x] = min(max(x, m), M)

les « opérations saturées » seront des versions cadrées des opérations usuelles :

a [+] b = [a + b], a [×] b = [a × b]…

Une fois M atteint, de nouvelles additions ne changent rien. De même, si m est atteint, de nouvelles soustractions ne changent rien.

Si le domaine de cette arithmétique saturée est de –100 à 100, nous aurons successivement :

• 52 + 42 = 94 mais 60 + 43 = 100
• 50 – 30 +60 = 80 mais 50 + 60 – 30 = 70
• (60 + 43) − 150 = −50
• 43 − 150 = −100
• 60 + (43 − 150) = −40
• 10 × 9 = 90 mais 10 × 11 = 100
• 99 × 99 = 100
• 30 × 3 = 90 mais 30 × (5 − 1) = 100
• 30 × 5 − 30 × 1 = 70 car 100 – 30 = 70

On a toujours x [+] M = M, et la borne supérieure est dite absorbante pour l'addition. De même, on a toujours m [–] x = m, et la borne inférieure devient absorbante à gauche pour la soustraction.

Les propriétés usuelles (associativité, distributivité) ne sont pas respectées ; la borne supérieure du domaine est absorbante pour l'addition, la borne inférieure est absorbante pour la soustraction ; la soustraction n'est pas l'inverse exact de l'addition : 70 + 40 = 100 mais 100 – 70 = 30…

Comme on peut le voir, ce genre d'arithmétique n'est pas très plaisante sur le plan théorique, mais elle a un important rôle à jouer en termes de dispositifs matériels et d'algorithmes.

En général, les processeurs arithmétiques n'utilisent pas d'arithmétique saturée, mais plutôt une arithmétique modulaire. Un résultat excessif devient petit, comme dans une horloge où le nombre de minutes ou de secondes, après 59, devient zéro.

Dans les traitements non signés, 2ⁿ – 1 est suivi par 0, et en cas de résultat excessif, seuls les n bits inférieurs sont retenus. Pour des entiers signés sur 16 bits, la plage de valeurs va de –(2^15) à (2^15) – 1. Le résultat a + b sera donné tel quel s'il est inférieur à 32 768, sinon le processeur donnera (a + b) – 65 536, et un résultat positif excessif sera rendu négatif (non sans armer un indicateur de débordement).

De réalisation un peu plus difficile, l'arithmétique saturée peut être considérée comme plus réaliste. Sur un octet, il est moins surprenant d'avoir un résultat de 127 au lieu de 130, que d'avoir –126 au lieu de 130. Les débordements des additions et multiplications peuvent être détecté par un test simple (résultat = borne max), dès lors que la borne maximale n'est pas admise comme donnée.

Cette arithmétique permet des algorithmes efficaces, notamment en matière de traitement du signal. Pour ajuster un volume sonore, la saturation est moins dangereuse qu'un son considéré comme trop faible… car au-delà du maximum admissible.

L'arithmétique saturée est maintenant disponible en C, C++, Eiffel, Python, et surtout Ada, qui en facilite l'usage, pour une meilleure maîtrise des débordements de valeurs.

Cette approche sera pleinement efficace quand les opérations max/min seront réalisées bit à bit, au niveau le plus bas, permettant un cadrage sans ces branchements qui actuellement perturbent l'exécution en mode pipe-line du flot d'instructions.

La norme virgule flottante IEEE, la meilleure approximation actuelle d'une arithmétique réelle, a repris une idée de Konrad Zuse (1938), selon laquelle une forme de saturation peut être introduite par la production de codes + infini ou –infini en cas de débordement, et leur transmission aux opérations ultérieures. Cela évite que ces opérations ultérieures en viennent à produire des résultats « raisonnables » mais faux.

L'arithmétique saturée convient bien à la modélisation des arithmétiques archaïques.

Elle convient également bien à l'expression des apprentissages.

• G. A. Constantinides, P. Y. K. Cheung, and W. Luk. Synthesis of Saturation Arithmetic Architectures

• SARITH: Safe ARITHmetic – A Progress Report: Report on a saturation arithmetic component for Eiffel.