- Arithmétique saturée
-
Cette arithmétique opère dans un domaine de valeurs limité par deux bornes, disons m et M. Une opération en arithmétique saturée fournit des résultats tels que :
- Si le calcul donne un nombre inférieur au plus petit nombre représentable m, alors m est produit.
- Si le calcul donne un nombre supérieur au plus grand nombre représentable M, alors M est produit.
Cela est particulièrement utilisé en informatique, et, notamment, en traitement du signal.
Sommaire
Présentation
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.
Exemple
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
Propriétés
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...
Discussion
Comme on peut le voir, ce genre d'arithmétique n'est pas très plaisante au 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ù après midi, il est une heure. Dans les traitements non signés, 2^n - 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, a+b sera donné tel quel s'il est inférieur à 32768, sinon le processeur donnera (a+b)-65536, 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 max 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.
Le standard virgule flottante IEEE, la meilleure approximation actuelle d'une arithmétique réelle, a repris une idée de K. 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 par les opérations ultérieures. Cela évite que ces opérations ultérieures en viennent à produire des résultats "raisonnables" mais faux.
Divers
L'arithmétique saturée convient bien à la modélisation des arithmétiques archaïques.
Elle convient également bien à l'expression des apprentissages.
Références
- 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.
Wikimedia Foundation. 2010.
