Бинарный алгоритм Евклида

     НОД(2*a, 2*b) = 2*НОД(a,b)
     НОД(2*a, b) = НОД(a,b) при нечетном b,

Он иллюстрируется следующей программой:

 m:= a; n:=b; d:=1;
 {НОД(a,b) = d * НОД(m,n)}
 while not ((m=0) or (n=0)) do begin
 if (m mod 2 = 0) and (n mod 2 = 0) then begin
 d:= d*2; m:= m div 2; n:= n div 2;
 end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
 m:= m div 2;
 end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
 n:= n div 2;
 end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
 m:= m-n;
 end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin
 n:= n-m;
 end;
 end;
 {m=0 => ответ=d*n; n=0 => ответ=d*m}