Cours de robustesse a Nancy

Cours de robustesse a Nancy

46

pages

English

Documents

Écrit par
Sylvain Pion

Publié par
Zodaj

Lire

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

46

pages

English

Ebook

Lire

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Nombre de lectures

32

Langue

English

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) Voir

Publié par

Nombre de lectures

32

Langue

English

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

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×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

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

© 2010-2024 YouScribe

Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts