Lehmer's GCD algorithm: Difference between revisions

Revision as of 18:18, 7 January 2015

Revision as of 20:04, 15 January 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|basebases]], say ''β'' = 1000 or ''β'' = 2³².

== Algorithm ==