Cours de robustesse a Dijon

Sylvain Pion

Description

Bases d’arithmetiquepour le calcul geometriqueSylvain PionINRIA Sophia AntipolisPlan Liens entre la geometrie et l’arithmetique Calcul ottant Calcul exact Calcul modulaire Bornes de separations Filtres arithmetiques Implantation dans CGAL1Introduction2Exemples de predicats geometriquespositiveC1orientation pqC2 C’1r p’C’2p negativeorientationx(p)

Informations

• Publié par: Musar
• Nombre de lectures: 38
• Langue: Français

Extrait

Basesd’arithm´etique pourlecalculg´eom´etrique

Sylvain Pion

INRIA

Sophia

Antipolis

•

•

•

•

•

•

•

Liensentrelage´om´etrieet

Calcul flottant

Calcul exact

Calcul modulaire

Bornes de separations ´

Filtresarithme´tiques

Implantation dans CGAL

Plan

l’arithm´etique

1

Intro

duction

2

Exemplesdepre´dicatsge´ome´triques

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

Pre´dicatde

Sylvain Pion

deg ´ 2 re.

3

Sylvain

Pion

Exemples

de

constructions

g´eom´etriques

4

Delage´ome´triea`l’arithm´etique

Algorithmege´om´etrique

Sylvain Pion

⇒tsurtcoisn)s(pr´edicats&congsnomoe´rte´euqi´eOptira

⇒nestffieic/soc´neeonrdooscleurssueqirbe´glasnoitarpOe´ √ . . .)

⇒aritionseratOp´(see´mhuqit+,−,×,÷,

5

Arithme´tique⇒eetrieom´G´

Coˆuteque´ittimh’lraed⇒et´xilempComhse´goe´mteiruqesetiroglasedspmetn

Arithm´etiqueorppe´hcea⇒esemderp`lborostbuseesglroedasse´gtimhetrieom´ques

Sylvain Pion

6

Lemod`eleReal-RAM

Mode`ledecalculateurr´eel`aacce`sale´atoire(RAM=Randomaccessmachine).

Mod`eleth´eoriqueducomportementdel’arithm´etiquer´eellesurordinateur.

•Toutes lesnsiotare´poitarquti´ehmntunˆutelrseseussloc´reetemps O(1) (et sont exactes).

•cuoceslleer´esbltnepraaielvstuseoTemoire´mecapse)1(O.

Lesanalysesdecomplexit´edesalgorithmesg´eome´triquessontfaites traditionnellementdanscemode`le.

Sylvain Pion

7

Relationaveclare´alite´desordinateurs?

Deux approches :

•Calcul flottant,appchro´e.

•Calcul exact,plus lent.

Pourlag´eom´etrie:quelleapprocheest-ellelameilleureenpratique?

Quelestlev´eritablecoˆutdel’approcheexacte?

8

Calcul

flottant

9

Standard IEEE 754

Standardisationdesop´erationsflottantesdebasedesordinateurs(1985). Repre´sentationmachinede(−1) s ×1.m×2 e ourladou(ptsbi):oisi46,npelbce´r s exposant mantisse 1 11 52

•5postion´era:+,− ×,÷, √ ,

•4 modes d’arrondisnoe(rembprrese´ebatn,)elsrevchrospluup:a0, vers+∞, vers−∞.

•Valuesrpse´iclase:+∞,−∞d´normaux, NaNs. , e

•Relativement bien suivie par l’industrie (langages, compilateurs, processeurs).

Voir ://tsvehehtt:pcom/cginollasch.feeei/gnidoc/xedltm.hatlo

Sylvain Pion

10