Cours de robustesse a Nancy

Sylvain Pion

Description

Robustness issues in CGAL :arithmetics and the kernelSylvain PionINRIA Sophia AntipolisPlan Links between geometry and arithmetics Floating point arithmetic Exact arithmetic Arithmetic lters CGAL implementation1Introduction2Examples of geometric predicatespositiveC1orientation pqC2 C’1r p’C’2p negativeorientationx(p)

Informations

• Publié par: Zodaj
• Nombre de lectures: 32
• Langue: English

Extrait

Robustness issues in arithmetics and the

Sylvain Pion

INRIA Sophia Antipolis

CGAL kernel

:

•

•

•

•

•

Links between geometry and

Floating point arithmetic

Exact arithmetic

Arithmetic filters

CGAL implementation

Plan

arithmetics

1

Intro

duction

2

Examples of geometric predicates

orientation(p, q r) = , sign((x(p)−x(r))×(y(q)−y(r))−(x(q)−x(r))×(y(p)−y(r)))

Predicate of

Sylvain Pion

degree 2.

3

Sylvain

Pion

Examples

of

geometric

constructions

4

From geometry to arithmetic

Geometric algorithm

Sylvain Pion

⇒Geometric operations (predicates and constructions)

⇒Algebraic operations over coordinates/coefficient √ . . .)

− ⇒Arithmetic operations (+, ,×,÷,

5

Arithmetic⇒Geometry

Costof arithmetic⇒Timecomplexityof geometric algorithms

Approximatethritimeca⇒ssenortsubproblems of geometric algorithms

Sylvain Pion

6

The Real-RAM model

Real computer model with random access (RAM = Random access machine).

Theoretical model specifying the behavior of real arithmetic on computers.

•All arithmeticoperationsover reals costO(1) time(and are exact).

•All real variables takeO(1) memory space.

Complexity analyses of geometric algorithms are traditionnaly performed within this model.

Sylvain Pion

7

Relationship with the reality of computers ?

Two approaches :

•Floating point arithmetic,approximate.

•Exact arithmetic,slower.

For geometry : which approach is the best in practice ?

What is the precise cost of the exact approach ?

8

Floating

point

arithmetic

9

IEEE 754 Standard

Standardization of basic FP operations on computers (1985). Machine representation of(−1) s ×1.m×2 e (for double precision, 64 bits):

s exponent 1 11

•5 operations:+,−,×,÷, √

mantissa 52

•4 rounding modes: to nearest (representable number), towards0, towards +∞, towards−∞.

•Special values:+∞,−∞, denormals, NaNs.

•supported by the industry (languages, compilers, processors).Relatively well

Ref :/cgi.comaschholletev/:s/thptmlhtt.oafleeei/gnidoc/xedn

Sylvain Pion

10