42
правки
Изменения
→Двоичный алгоритм Евклида
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
Можно показать<ref>http://maths-people.anu.edu.au/~brent/pd/rpb183pr.pdf Twenty years' analysis of the Binary Euclidean Algorithm</ref>, что этот алгоритм, в среднем на 60% более эффективен, чем классический. Но, к сожалению, в худшем случае он работает за <tex>O(\log^2\min(a, b))</tex>
===Расширенный алгоритм Евклида===
