Revision as of 11:55, 20 January 2011 edit Yobot (talk \| contribs) Bots 4,733,870 edits m Fixed/removed {{expand}} + WP:CHECKWIKI error fixes + general fixes, removed: {{Expand\|date=June 2009}} using AWB (7552) ← Previous edit		Revision as of 13:13, 23 January 2011 edit undo Yobot (talk \| contribs) Bots 4,733,870 edits m WP:CHECKWIKI error 61 fixes + general fixes, References after punctuation per WP:REFPUNC and WP:PAIC using AWB (7510) Next edit →
Line 2: == Algorithm == Lehmer noted that that most of the [[quotient]]s from each step of the division part of the standard algorithm are small. (For example, [[Donald Knuth\|Knuth]] observed that the quotients 1, 2, and 3 comprise 67.7% of all quotients.<ref name="knuth2">[[Donald Knuth\|Knuth]], ''[[The Art of Computer Programming]] vol 2 "Seminumerical algorithms"'', chapter 4.5.3 Theorem E.</ref>.) Those small quotients can be identified from only a few leading digits. Thus the algorithm starts by splitting off those leading digits and computing the sequence of quotients as long as it is correct. Say we want to obtain the GCD of the two integers ''a'' and ''b''. Let ''a'' ≥ ''b''. Line 37: == References == * Kapil Paranjape, [http://www.imsc.res.in/~kapil/crypto/notes/node11.html Lehmer's Algorithm] {{DEFAULTSORT:Lehmer's Gcd Algorithm}}

Lehmer's GCD algorithm: Difference between revisions