Algorithme d'Euclide

Algorithme d’Euclide

ann´eeuniversitaire2013

L’objectifdecettese´ancedetravauxpratiquesestdeve´rifierexpe´rimentalement
lesre´sultatsducoursconcernantlecalculduPGCDdedeuxentiers:le
th´eor`emedeG.Lam´e,l’approchebinaireetl’algorithmed’Euclidee´tendu.

1Nombred’it´eration
Etantdonne´sdeuxentierspositifsaetb,b≤a, on noteI(a, b) le nombre
d’it´erationdel’algorithmed’Euclidepourde´terminerpgcd(a, b).
1. Implanterullong pgcd(ullong a,ullong b)en utilisant l’algorithme
it´eratif.Ve´rifierlebonfonctionnementdevotrefonction.
2. Implanterullong iter(ullong a,ullong b)qui retourne le nombre
d’it´erationsdel’algorithmed’Euclide.
3. Utilisergnuploturpoprrese´eerntrgelehpaaledcnofitno
a7→supI(a, b).
0≤b≤a
4.idempourlecouˆtmoyen
X
1
a7→I(a, b).
a
0≤b≤a

2 PGCDbinaire
Implanter l’algorithme du PGCD binaire sur les entiers de 64 bits. Com-
parer les performance du PGCD binaire avec celui de l’algorithme d’Euclide.

1

Fig.die1moC–xelpe´ti’ledgoalthrid’meclEu

3Euclidee´tendu
1.Implanteruneversionre´cursivevoid bbr(ullong a, ...*u, ullong
b, ...*v)de l’algorithme d’Euclide.
2.Implanteruneversionit´erativevoid bbi(ullong a, ...*u, ullong
b, ...*v)de l’algorithme d’Euclide.
3.V´erifierlebonfonctionnementdecesdeuximplantations.
4.Fairedesversions“verbeuses”quitracentl’´evolutiondesvariablesau
coursdes´etapesinterme´diaires.

2