Revision as of 17:43, 16 August 2008 edit Jafet (talk \| contribs) 940 edits Remove incorrect citation ← Previous edit		Revision as of 18:17, 16 August 2008 edit undo Michael Hardy (talk \| contribs) Administrators 210,577 edits m →Algorithm: punctuation correction Next edit →
Line 2: == Algorithm == [[Derrick Henry Lehmer\|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.) Say we want to obtain the GCD of the two integers ''a'' and ''b''. Let <math>\textstyle a \ge b</math>.

Lehmer's GCD algorithm: Difference between revisions