42
правки
Изменения
→Двоичный алгоритм Евклида
Для начала, опишем еще несколько свойств <tex>gcd</tex>:
{{Утверждение
|id=l3
|statement=
Пусть <tex>a</tex> и <tex>b</tex> - натуральные числа, тогда
}}
Пользуясь этим, и утверждением [[#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>// первые два случая</font>
'''if''' <tex>\mathtt{a} \bmod 2 = 0:</tex>
'''if''' <tex>\mathtt{b} \bmod 2 = 0:</tex>
'''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b\: /\: 2)} \cdot 2</tex>
'''else'''
'''return''' <tex>\mathtt{binaryGcd(a\: /\: 2, b)}</tex>
<font color=green>// второй случай, только <tex>a</tex> и <tex>b</tex> поменяли местами</font>
'''if''' <tex>\mathtt{b} \bmod 2 = 0:</tex>
'''return''' <tex>\mathtt{binaryGcd(a, b\: /\: 2)}</tex>
<font color=green>// остается ретий случай. На самом деле, мы можем оставлять справа и <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>
===Расширенный алгоритм Евклида===
