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.

Contenu soumis à la licence CC-BY-SA. Source : Article Arithmétique saturée de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Arithmetique saturee — Arithmétique saturée 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, le plus petit nombre représentable est produit. Si le calcul donne un… …   Wikipédia en Français

  • Arithmétique Saturée — 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, le plus petit nombre représentable est produit. Si le calcul donne un nombre supérieur au plus… …   Wikipédia en Français

  • Arithmetique — Arithmétique L arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l appelle plus généralement la « science des… …   Wikipédia en Français

  • Arithmétique — L arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l appelle plus généralement la « science des… …   Wikipédia en Français

  • Opération arithmétique — Arithmétique L arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l appelle plus généralement la « science des… …   Wikipédia en Français

  • Modulo (informatique) — Une très grande part des calculs réalisés en informatique sont des calculs d arithmétique modulaire (d autres se font, par exemple, en arithmétique saturée). En effet, les données manipulées sont toujours représentées au final comme une suite… …   Wikipédia en Français

  • Notion de module — Pour les articles homonymes, voir Module. Un module est une unité de mesure conventionnelle adoptée pour régler les diverses parties d un ensemble (construction, machine...). Il correspond à la plus petite commune mesure que doivent posséder les… …   Wikipédia en Français

  • MODÈLES (THÉORIE DES) — «Modèle» est un terme qui appartient au vocabulaire de la plupart des sciences et qui a des significations multiples [cf. MODÈLE]. Ainsi, dans les sciences humaines, on entend généralement par modèle une théorie conçue pour expliquer un ensemble… …   Encyclopédie Universelle

  • MÉTALOGIQUE — Étude des propriétés des systèmes logiques. Une fois construit comme système, un formalisme peut lui même devenir objet d’étude. Les propriétés les plus importantes des systèmes formels sont les suivantes: tout d’abord, dans l’ensemble des… …   Encyclopédie Universelle

  • La Cene — La Cène La Cène Léonard de Vinci, 1494 1498 Tempera grassa sur gesso 460 × 880 cm …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”