Алгоритм Евклида

Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД) двух целых чисел.

Реализации на языке Глагол:

ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ; 
УКАЗ 
  ПОКА (a # 0) И (b # 0) ВЫП 
    ЕСЛИ a >= b ТО 
      a := a ОСТАТОК b 
    ИНАЧЕ 
      b := b ОСТАТОК a 
    КОН 
  КОН; 
  ВОЗВРАТ a + b 
КОН НОД;

Алгоритм вычитанием:

ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ; 
УКАЗ 
  ПОКА a # b ВЫП
    ЕСЛИ a > b ТО УМЕНЬШИТЬ(a, b)
    ИНАЧЕ УМЕНЬШИТЬ(b, a) КОН
  КОН;
  ВОЗВРАТ a
КОН НОД;

Алгоритм с самовызовом (рекурсивный):

ЗАДАЧА НОД(a, b: ЦЕЛ): ЦЕЛ; 
УКАЗ 
  ЕСЛИ a <= b ТО 
    ЕСЛИ a = 0 ТО ВОЗВРАТ b ИНАЧЕ ВОЗВРАТ НОД(b ОСТАТОК a, a) КОН 
  ИНАЧЕ 
    ЕСЛИ b = 0 ТО ВОЗВРАТ a ИНАЧЕ ВОЗВРАТ НОД(a ОСТАТОК b, b) КОН 
  КОН 
КОН НОД;

Пример выполнения последнего с выводом переменных при каждом вызове функции:

Вычисление НОД(123456, 6122256):
123456 6122256
72912 123456
50544 72912
22368 50544
5808 22368
4944 5808
864 4944
624 864
240 624
144 240
96 144
48 96
0 48
НОД(123456, 6122256) = 48

Время работы алгоритма Евклида составляет O(log a + log b) арифметических операций над натуральными числами.