ANALYSIS of EUCLIDEAN ALGORITHMS

Brigitte Vallée

Description

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

Sujets

• Clement
• Vallée
• Bourdon
• Analysis
• Balady
• Dynamical system
• Euclidean algorithm

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 82
• Langue: English

Extrait

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

fo

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

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

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

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

11T
:[0
,
1]
−→
[0
,
1]
,T
(
x
):=
x
−
x
for
x
6
=0
,T
(0)=0

An
execution
oftheEuclideanAlgorithm
(
x,T
(
x
)
,T
2
(
x
)
,...,
0)

=A
rationaltrajectory
oftheDynamicalSystem
([0
,
1]
,T
)

=a
trajectory
thatreaches
0
.

Thedynamicalsystemisacontinuousextensionofthealgorithm.

11T
(
x
):=
x
−
x

T
[
m
]
:]
m
1+1
,m
1[
−→
]0
,
1[
,

h1T
[
m
]
(
x
):=
x
−
m

[]m

]:0,[111−→
]
m
+1
,m
[

1h
[
m
]
(
x
):=
m
+
x