42
правки
Изменения
→Двоичный алгоритм Евклида
Мы получили очень простой алгоритм, который считает НОД за логарифмическое время. However, we can do better.
===Двоичный алгоритм Евклида===
Идея улучшения: давайте вместо долгого деления ограничимся вычитаниями и битовыми сдвигами.
Для начала, опишем еще несколько свойств <tex>gcd</tex>:
{{Утверждение
|statement=
Пусть <tex>a</tex> и <tex>b</tex> - натуральные числа, тогда
* <tex>\gcd(2a, 2b) = 2\cdot\gcd(a, b)</tex>
* <tex>\gcd(2a, 2b + 1) = \gcd(a, 2b + 1)</tex>
|proof=
Тривиальным образом следует из определения
}}
===Расширенный алгоритм Евклида===
