Бинарный алгоритм вычисления НОД

Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм "быстрее" обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Возможно, алгоритм был известен еще в Китае 1-го века, но опубликован был лишь в 1967 году израильским физиком и программистом Джозефом Стайном. Он основан на использовании следующих свойств НОД: * НОД(2m, 2n) = 2 НОД(m, n), * НОД(2m, 2n+1) = НОД(m, 2n+1), * НОД(-m, n) = НОД(m, n)