Lehmer's GCD algorithm: Difference between revisions

Revision as of 16:14, 22 February 2016

Revision as of 18:09, 6 June 2016

Line 1:

'''Lehmer'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 ==