L'Arithmétique d'intervalle pour les prédicats géométriques
|
| L'Arithmétique d'intervalle pour les prédicats géométriques |
|
L'arithmétique d'intervalle permet d'accélérer les calculs exacts, à faible coût, c'est un filtre arithmétique. Cela concerne la plupart des tests géométriques, qui ont besoin d'être effectués de manière exacte, en particulier les signes de déterminants et d'expressions polynomiales plus générales.
Le principe de base du calcul par intervalle est de représenter un nombre par un intervalle qui le contient. Les opérations successives (les 4 opérations de base et la racine carrée) sur ces intervalles préservent cette inclusion. De fait, pour déterminer le signe d'une variable, il suffit de regarder si l'intervalle qui le représente contient zéro.
On sait qu'il y a une grande probabilité pour que le filtre flottant suffise, à savoir dans tous les cas, sauf ceux qui sont dégénérés, ou presque.
Il existe différentes sortes de filtres. Statique, semi-statique, et dynamique. Les filtres statiques supposent des bornes sur les entrées, et ne supportent pas toutes les opérations, mais ils sont les plus rapides (quasi aussi rapide que le calcul flottant), car la majoration de l'erreur est calculée à la compilation. Les semi-statiques calculent la borne d'erreur à l'execution, de manière simple, elle est donc plus précise que dans le cas précédent, mais le calcul est aussi plus lent. Enfin le cas dynamique maintient la borne d'erreur de chaque variable, c'est le cas de l'arithmétique d'intervalle. La méthode présente une simplicité d'utilisation et une généralité que n'ont pas les autres types de filtre. De plus, des efforts ont été faits afin d'obtenir une implantation la plus efficace possible, le surcoût face au calcul flottant étant d'un facteur 3 à 8 sur le prédicat, ce qui présente un surcoût final tolérable sur une application.
Concernant l'implantation, le code source (version 1998-09-29) est disponible librement pour tous usages. Il contient deux interfaces C++, une en C, et une avec des macros. Les temps de calculs sont soit comparables, soit nettement meilleurs que ceux des implantations classiques telles que la bibliothèque Profil/BIAS.
L'implantation est basée sur l'utilisation des modes d'arrondi de la FPU. La particularité de cette implantation est qu'elle ne nécessite pas de changements constants du mode d'arrondi, du fait de la représentation choisie, qui stocke l'opposé de la borne inférieure de l'intervalle. De ce fait, le code est performant, et laisse plus de champ à l'optimiseur du compilateur.
Consultez ma bibliographie pour plus de détails.