46 Pages
English

# Cours de robustesse a Nancy

-

Learn all about the services we offer

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)

Subjects

##### Formal sciences

Informations

Robustness issues in arithmetics and the
Sylvain Pion
INRIA Sophia Antipolis
CGAL kernel
:
Links between geometry and
Floating point arithmetic
Exact arithmetic
Arithmetic ﬁlters
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/coeﬃcient . . .)
Arithmetic operations (+, ,×,÷,
5
ArithmeticGeometry
Costof arithmeticTimecomplexityof geometric algorithms
Approximatethritimecassenortsubproblems 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×2e(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