Lehmer's GCD algorithm: Difference between revisions

Revision as of 18:19, 11 January 2020

Latest revision as of 18:19, 11 January 2020

Line 1:

{{short description|Fast greatest common divisor algorithm}}

'''LehmersLehmer's GCD algorithm''', named after [[Derrick Henry Lehmer]], is a fast [[greatest common divisor|GCD]] [[algorithm]], an improvement on the simpler but slower [[Euclidean algorithm]]. It is mainly used for big integers that have a representation as a string of digits relative to some chosen numeral system [[radix|base]], say ''β'' = 1000 or ''β'' = 2³².

== Algorithm ==