344
правки
Изменения
→Двоичный алгоритм Евклида
}}
Пользуясь этим, и утверждением [[#l2 | о НОДе нуля]], определим двоичный алгоритм Евклида (ниже будет дана рекурсивная реализация, для лучшей читаемости):
'''function''' <tex>\mathtt{binaryGcd(a, b)}:</tex> '''if''' <tex>\mathtt{a}</tex> == <tex>\mathtt{b}</tex> '''or''' <tex>\mathtt{b}</tex> == <tex>\mathtt{0}:</tex> '''return''' <tex>\mathtt{a}</tex> '''if''' <tex>\mathtt{a}</tex> == <tex>\mathtt{0}:</tex> '''return''' <tex>\mathtt{b}</tex> <font color=green"darkgreen">// первые два случая</font> '''if''' <tex>\mathtt{a} \bmod mod 2 = 0:</tex> '''if''' <tex>\mathtt{b} \bmod mod 2 = 0:</tex> '''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b\: /\: 2)} <tex>\cdot 2</tex>2
'''else'''
'''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b)}</tex> <font color=green"darkgreen">// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font> '''if''' <tex>\mathtt{b} \bmod mod 2 = 0:</tex> '''return''' <tex>\mathtt{binaryGcd(a, b\: /\: 2)}</tex> <font color=green"darkgreen">// остается третий случай. На самом деле, мы можем оставлять справа и <tex>a</tex>, и <tex>b</tex></font> <font color=green>// поэтому давайте всегда оставлять меньшее</font> '''if''' <tex>\mathtt{a} > \mathtt{b}:</tex> '''return''' <tex>\mathtt{binaryGcd((a - b)\: /\: 2, b)}</tex> '''return''' <tex>\mathtt{binaryGcd((b - a)\: /\: 2, a)}</tex>
Корректность данного алгоритма следует из того, что он на каждом шаге делает эквивалентные преобразования НОД(это следует из утверждений [[#l3 | о НОДе четных и нечетных]] и [[#l2 | о НОДе нуля]]).
