La lecture à portée de main
Description
Informations
Publié par | Force_IT |
Nombre de lectures | 110 |
Licence : |
En savoir + Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
|
Langue | Français |
Extrait
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