Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

2.3. A bináris legnagyobb közös osztó algoritmus

2.3. A bináris legnagyobb közös osztó algoritmus

Az eddigiek alapján algoritmus konstruálható a legnagyobb közös osztó meghatározására. Az algoritmus neve: Bináris lnko algoritmus.

Az algoritmus a két nemnegatív egész bináris felírásának alakjából indul ki. Az utolsó bit alapján a kiinduló problémát fokozatosan egyszerűbbé redukálja, amíg csak az egyik szám zérussá nem válik. Ekkor a legnagyobb közös osztó a másik redukált szám egy szorzóval korrigált értéke lesz. Munka közben az algoritmus csak egyszerű, hatékony gépi műveleteket - egész kivonás és jobbra eltolás (shift) - használ.

Legyen a két szám és és legyen . A kiszámításának feladata ekkor az alábbiak szerint redukálódik az utolsó bit szerint egyszerűbb feladattá:

2.2. Példa. Példa az algoritmusra: