Наибольший общий делитель двух целых чисел (алгоритм Евклида)

Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое нацело делит эти два числа. По определению НОД(0,0)=0.

Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b)=|a+b|, в других случаях последовательно находятся остатки ri от делений:

a на b-a=bq1+r1,
b на r1-b=r1q2+r2,
r1 на r2-r1=r2q3+r3,
. . . . . .
и т.д., пока rn+1 не станет равно нулю. Тогда НОД(a,b)=НОД(b,r1)=НОД(r1 ,r2)=...=НОД(rn-1 ,rn )=rn.

А вот как этот алгоритм описан в книге Д.Э. Кнута "Искусство программирования".

1) [Проверка] Если a<b, то a<->b.

2) [Нахождение остатка] Разделим a на b, и пусть остаток от деления будет равен r (где 0<=r<b).

3) [Сравнение с нулем] Если r=0, то выполнение алгоритма прекращается; b - искомое значение.

4) [Замещение] Присвоить a<-b, b<-r и вернуться к шагу 1.


Моя реализация данного алгоритма на Паскале:

function nod(a,b: integer):integer;
begin
if a<b then begin
a := a xor b;
b := a xor b;
a := a xor b;
end;
while not ((a=0) or (b=0)) do
if a >= b then a := a mod b else b := b mod a;
if a = 0 then result := b else result := a;
end;