Algorithm Ewclidaidd

Mewn mathemateg, mae'r algorithm Ewclidaidd, neu algorithm Euclid, yn ddull effeithiol ar gyfer cyfrifo'r rhannydd cyffredin mwyaf (greatest common divisor; GCD) dau gyfanrif a a b.

Algorithm Ewclidaidd

Enghraifft o'r canlynol	algorithm
Ffeiliau perthnasol ar Gomin Wicimedia

Dull Euclid o ddod o hyd i'r rhannydd cyffredin mwyaf (GCD) o ddau hyd cychwynnol BA a DC, gyda'r ddau wedi'u diffinio fel lluosrifau o hyd "uned" gyffredin. Mae hyd DC yn fyrrach, fe'i defnyddir i "fesur" BA, ond dim ond unwaith oherwydd bod gweddill EA yn llai na DC. Mae EA erbyn hyn yn mesur (dwywaith) y DC byrrach, gyda'r gweddill FC yn fyrrach nag EA. Yna, mae FC yn mesur (dergwaith) hyd EA. Oherwydd nad oes gweddill, mae'r broses yn dod i ben gyda FC yn GCD. Ar y dde, ceir esiampl o Algorithm Nicomachus ar y dde, gyda rhifau 49 a 21 yn rhoi GCD o 7 (yn deillio o Heath 1908:300).

Os yw a yn 210 a b yn 45 yna:

• os yw 210 yn cael ei rannu gan 45, yna ceir yr ateb 4, gweddil 30, felly: 210 = 4·45 + 30.
• os rhennir 45 gan 30, yna ceir yr ateb 1, gweddill 15, felly: 45 = 1·30 + 15.
• os rhennir 30 gyda 15, ceir yr ateb 2, gweddill 0, felly: 30 = 2·15 + 0.
• rhannydd cyffredin mwyaf 210 a 45, felly, yw 15.

Yn grynno, yr Algorithm Ewclidaidd yw'r rhif mwyaf sy'n rhannu dau rif, heb adael gweddill.

Enwyd yr algorithm hwn ar ôl y mathemategydd Groegaidd Euclid, a ddisgrifiodd ef am y tro cyntaf yn ei Elfennau (tua 300 CC). Mae'n enghraifft o algorithm, gweithdrefn gam-wrth-gam, ar gyfer perfformio cyfrifiant yn unol â rheolau a ddiffiniwyd yn glir, ac mae'n un o'r algorithmau hynaf sy'n cael eu defnyddio'n gyffredin heddiw. Gellir defnyddio Algorithm Ewclidaidd i leihau ffracsiynau i'w ffurf symlaf, ac mae'n rhan o lawer o gyfrifiannau rhif-damcaniaethol a chryptograffig eraill.

Enghraifft arall

Mae'r Algorithm Ewclidaidd yn seiliedig ar yr egwyddor nad yw'r rhannydd cyffredin mwyaf (GCD) o ddau rif ddim yn newid os disodlir y gwahaniaeth yn y rhif mwyaf gan y rhif lleiaf. Er enghraifft, 21 yw'r GCD o 252 a 105 (h.y. 252 = 21 × 12 a 105 = 21 × 5), a'r un rhif 21 hefyd yw'r GCD o 105 a 252 - 105 = 147. Gan fod y disodli hwn yn lleihau'r rhif mwyaf o'r ddau, mae ailadrodd y broses hon yn rhoi sawl pâr o rifau, nes bod y ddau rif yn dod yn gyfartal.

Pan ddigwydd hynny, hwy yw'r rhannydd cyffredin mwyaf (GCD) y ddau rif gwreiddiol. Trwy wrthdroi'r camau (h.y. eu rhoi o chwith), gellir mynegi'r GCD fel cyfanswm y ddau rif gwreiddiol, bob un wedi'i luosi gan gyfanrifau positif neu negatif, e.e. 21 = 5 × 105 + (-2) × 252. Gall y GCD, bob amser, gael ei fynegi fel hyn; "Unfathiant Bézout" (Bézout's identity) yw'r enw am hyn.

Datblygiad diweddar

Gall y fersiwn o'r algorithm Ewclidaidd a ddisgrifir uchod gymryd nifer o gamau tynnu i ddod o hyd i'r GCD pan fo un o'r rhifau a roddir yn llawer mwy na'r llall. Mae fersiwn fwy effeithiol o'r algorithm yn mynd i'r afael â'r camau hyn, gan ddisodli'r mwyaf o'r ddau rif gan ei weddill pan gaiff ei rannu gan y lleiaf o'r ddau rif. Mae'r algorithm yn stopio wrth gyrraedd gweddill o sero. Gyda'r gwelliant hwn, ni fydd fyth angen mwy na phum gwaith y nifer o ddigidau (sylfaen 10) na'r cyfanrif lleiaf. Profwyd hyn gan Gabriel Lamé yn 1844, ac mae'n nodi dechrau damcaniaeth cymhlethdod cyfrifiadurol. Datblygwyd dulliau ychwanegol o wella effeithiolrwydd yr algorithm yn yr 20g.