An Algorithm that Computes a Lower Bound on the Distance Between a Segment and $Z^2$

Vincent Lefevre (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We give a fast algorithm for computing a lower bound on the distance between a straight line and the points of a regular grid. This algorithm is used to find worst cases when trying to round the elementary functions correctly in floating-point arithmetic, which consists in returning the machine number that is the closest (there are other rounding modes) to the exact result.

Nous donnons un algorithme rapide permettant de calculer une minoration de la distance entre un segment de droite et les points d'une grille régulière. Cet algorithme est utilisé pour trouver les pires cas lorsque l'on arrondit exactement les fonctions élémentaires en arithmétique à virgule flottante, ce qui consiste à renvoyer le nombre machine le plus proche (il existe d'autres modes d'arrondi) du résultat exact.

Mots clés: Elementary Functions; Floating-Point Arithmetic; Rounding

Mots clés: Arithmétique virgule-flottante; Arrondi; Fonctions élémentaires

Domaines: Informatique [cs]

Vincent Lefevre. An Algorithm that Computes a Lower Bound on the Distance Between a Segment and $Z^2$. [Research Report] LIP RR-1997-18, Laboratoire de l'informatique du parallélisme. 1997, 2+9p. ⟨hal-02101812⟩