Инт-9 2018: Усложненные арифметические алгоритмы

В бинарном алгоритме Евклида не используются операции деления и остатка, а используется только проверка на чётность и деление на 2. Идея бинарного алгоритма Евклида следующая:
\(НОД(a,b)=2НОД(a/2,b/2)\), если \(a\) и \(b\) четные,
\(НОД(a,b)=НОД(a/2,b)\), если \(a\) четное, \(b\) нечетное,
\(НОД(a,b)=НОД(a,b/2)\), если \(a\) нечетное, \(b\) четное,
\(НОД(a,b)=НОД(a-b,b)\), если \(a\) и \(b\) нечетные, \(a\ge b\).

Реализуйте бинарный алгоритм Евклида для вычисления НОД двух чисел.