Algorithm Ewclidaidd: Gwahaniaeth rhwng fersiynau
Cynnwys wedi'i ddileu Cynnwys wedi'i ychwanegu
Dim crynodeb golygu |
Trwsio dolennau rhywogaethau a manion eraill using AWB |
||
Llinell 1:
[[Delwedd:Euclid's algorithm Book VII Proposition 2 3.png|300px|bawd|dde|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 [[Lluosi|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).]]
Mewn [[mathemateg]], mae'r '''algorithm Ewclidaidd''', neu '''algorithm Euclid''', yn ddull effeithiol ar gyfer cyfrifo'r rhannydd cyffredin mwyaf (''greatest common divisor''; GCD) dau [[cyfanrif|gyfanrif]] '''a''' a '''b'''.
Os yw '''a''' yn 210 a '''b''' yn 45 yna:
Llinell 20:
;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]].<ref>{{Harvnb|Tattersall|2005|pp=72–76}}</ref>
==Cyfeiriadau==
| |||