ANALYSIS of EUCLIDEAN ALGORITHMS

125

pages

English

Documents

Écrit par
Brigitte Vallée

Publié par
profil-urra-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

125

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-urra-2012

Nombre de lectures

Langue

English

ANALYSIS of EUCLIDEAN ALGORITHMS An Arithmetical Instance of Dynamical Analysis Dynamical Analysis := Analysis of Algorithms + Dynamical Systems Brigitte Vallee (CNRS and Universite de Caen, France) Results obtained with : Ali Akhavi, Viviane Baladi, Jeremie Bourdon, Eda Cesaratto, Julien Clement, Benoıt Daireaux, Philippe Flajolet, Loıck Lhote, Veronique Maume.

dynamical systems

v– dynamical

euclid algorithm

up?1 up?1

benoıt daireaux

iv– euclidean algorithms

algorithms

u1 u1

results obtained

euclidean algorithms

Voir

Publié par

profil-urra-2012

Nombre de lectures

Langue

English

ANALYSISofEUCLIDEANALGORITHMS

AnArithmeticalInstanceofDynamicalAnalysis

DynamicalAnalysis:=

AnalysisofAlgorithms+DynamicalSystems

Brigitte
Valle´e
(CNRSandUniversite´deCaen,France)

Resultsobtainedwith:

Ali
Akhavi
,Viviane
Baladi
,Je´re´mie
Bourdon
,

Eda
Cesaratto
,Julien
Cle´ment
,Benoıˆt
Daireaux
,

Philippe
Flajolet
,Loı¨ck
Lhote
,Ve´ronique
Maume
.

PlanoftheTalk

I–TheEuclidAlgorithm,andtheunderlyingdynamicalsystem

II–TheotherEuclideanAlgorithms

III–Probabilistic–anddynamical–analysisofalgorithms

IV–Euclideanalgorithms:theunderlyingdynamicalsystems

V–DynamicalanalysisofEuclideanalgorithms

PlanoftheTalk

I–TheEuclidAlgorithm,andtheunderlyingdynamicalsystem

II–TheotherEuclideanAlgorithms

III–Probabilistic–anddynamical–analysisofalgorithms

IV–Euclideanalgorithms:theunderlyingdynamicalsystems

V–DynamicalanalysisofEuclideanalgorithms

input
(
u,v
)
,itcomputesthe
gcd
of
u
and
v
,

ehtnO

together

htiw

eht

deunitnoC

rFnoitca

xEnoisnap

.v/u

ehT

(standard)EuclidAlgorithm:thegrandfatherofallthealgorithms.

,pm1+...1+2m1+1m1=vu:vufoEFC.htpedehtsip.stigidehteras’imeht,vdnaufodcgehtsipu0=1+pu0+pupm=1−pu1−pu<pu<0pu+1−pu1−pm=2−pu+...=...2u<3u<03u+2u2m=1u1u<2u<02u+1u1m=0u1u≥0u;u=:1u;v=:0u
The(standard)EuclidAlgorithm:thegrandfatherofallthealgorithms.

Ontheinput
(
u,v
)
,itcomputesthe
gcd
of
u
and
v
,

togetherwiththe
ContinuedFractionExpansion
of
u/v

.v/ufonoisnapxEnoitcarFdeunitnoC

u;u=:u;v=:u010

u
0
=
m
1
u
1
+
u
2


u
1
=
m
2
u
2
+
u
3
...
=
...
+

u
p
−
2
=
m
p
−
1
u
p
−
1
+
u
p
u
p
−
1
=
m
p
u
p
+0

u
p
isthe

≥u1

0
<u
2
<u
1
0
<u
3
<u
2



0
<u
p
<u
p
−
1

u
p
+1
=0

.htpedehtsip.stigidehteras’meht,vdnaufodcgi

FCEfouv:uv=m1+m21+.1..1+1mp,
The(standard)EuclidAlgorithm:thegrandfatherofallthealgorithms.

Ontheinput
(
u,v
)
,itcomputesthe
gcd
of
u
and
v
,

togetherwiththe
ContinuedFractionExpansion
of
u/v

C.v/ufonoisnapxEnoitcarFdeunitno

u
0
:=
v
;
u
1
:=
u
;
u
0
≥
u
1

u
0
=
m
1
u
1
+
u
2


u
1
=
m
2
u
2
+
u
3
...
=
...
+

u
p
−
2
=
m
p
−
1
u
p
−
1
+
u
p
u
p
−
1
=
m
p
u
p
+0


0
<u
2
<u
1
0
<u
3
<u
2



0
<u
p
<u
p
−
1

u
p
+1
=0

u
p
isthe
gcd
of
u
and
v
,the
m
i
’sarethe
digits
.
p
isthe
depth
.

uCFEof:
v

1u=,1v+m11+m2.1..+mp

0[(metsySlacimanyDehtfoyrotcejartlanoitarA=)0,...,)x(2T,)x(T,x(mhtiroglAnaedilcuEehtfonoitucexenA0=)0(T,0=6xrofx1−x1=:)x(T,]1,0[→−]1,0[:Terehw,)ix(T=1+ixroix1−ix1=1+ixsanettirwnehtsi1+iu+iuim=1−iunoisividTheunderlyingEuclideandynamicalsystem(I).

e(
u
1
,u
0
)
is:

hThetraceoftheexecutionoftheEuclidAlgorithmon

T(
u
1
,u
0
)
→
(
u
2
,u
1
)
→
(
u
3
,u
2
)
→
...
→
(
u
p
−
1
,u
p
)
→

.(
u
p
+1
,u
p
)=

1(0
,u
p
)

−iuiu=:ixlanoitarehtyb)1−iu,iu(riapregetniehtecalpeR.mhtiroglaehtfonoisnetxesuounitnocasimetsyslacimanydehT.0sehcaertahtyrotcejarta=)T,]1,
.mhtiroglaehtfonoisneTheunderlyingEuclideandynamicalsystem(I).

tfor
x
6
=0
,T
(0)=0

x11T
:[0
,
1]
−→
[0
,
1]
,T
(
x
):=
x
−
x

e11x
i
+1
=
x
−
x
or
x
i
+1
=
T
(
x
i
)
,
where
ii

sThedivision
u
i
−
1
=
m
i
u
i
+
u
i
+1
isthenwrittenas

uuReplacetheintegerpair
(
u
i
,u
i
−
1
)
bytherational
x
i
:=
i
.
u1−i

oThetraceoftheexecutionoftheEuclidAlgorithmon
(
u
1
,u
0
)
is:

u(
u
1
,u
0
)
→
(
u
2
,u
1
)
→
(
u
3
,u
2
)
→
...
→
(
u
p
−
1
,u
p
)
→
(
u
p
+1
,u
p
)=(0
,u
p
)

nitnocasimetsyslacimanydehT.0sehcaertahtyrotcejarta=)T,]1,0[(metsySlacimanyDehtfoyrotcejartlanoitarA=)0,...,)x(2T,)x(T,x(mhtiroglAnaedilcuEehtfonoitucexenA
TheunderlyingEuclideandynamicalsystem(I).

ThetraceoftheexecutionoftheEuclidAlgorithmon
(
u
1
,u
0
)
is:

(
u
1
,u
0
)
→
(
u
2
,u
1
)
→
(
u
3
,u
2
)
→
...
→
(
u
p
−
1
,u
p
)
→
(
u
p
+1
,u
p
)=(0
,u
p
)