Как-то некто David Fetter написал пост о том, как можно вычислить НОД (Наибольший Общий Делитель, а не одноименное братство) двух чисел с помощью PostgreSQL. И назвал это «быстрым способом».

1. WITH RECURSIVE t(a, b) AS (
2.     VALUES (38, 12)
3. UNION ALL
4.     SELECT least(a, b), abs(a - b) FROM t
5.     WHERE abs(a - b) > 0
6. )
7. SELECT a AS gcd FROM t
8. WHERE a = b;

* This source code was highlighted with Source Code Highlighter.

Однако моя горячая натура, честно просидевшая 5 лет в университете, возжелала не согласиться. Из этого, собственно, и началось моё исследование.

Для начала действительно быстрый вариант:

1. WITH RECURSIVE t(a, b) AS (
2.     VALUES (38, 12)
3. UNION ALL
4.     SELECT b, mod(a,b) FROM t
5.     WHERE b > 0
6. )
7. SELECT a AS gcd FROM t WHERE b = 0;

* This source code was highlighted with Source Code Highlighter.

Я уверен, что многие узнают в этой реализации знаменитый алгоритм Евклида. В данном конкретном примере мы находим НОД(38, 12), который равен 2.

Чтобы облагородить и облегчить в дальнейшем использование этого чуда, было решено написать функцию:

1. CREATE OR REPLACE FUNCTION gcd(bigint, bigint) RETURNS bigint AS
2. $$
3. WITH RECURSIVE t(a, b) AS (
4.     VALUES (abs($1) :: bigint, abs($2) :: bigint)
5. UNION ALL
6.     SELECT b, mod(a,b) FROM t
7.     WHERE b > 0
8. )
9. SELECT a AS gcd FROM t WHERE b = 0;
10. $$
11. IMMUTABLE
12. STRICT
13. LANGUAGE SQL;

* This source code was highlighted with Source Code Highlighter.

Прошу обратить внимание на некоторые усовершенствования:

• работает функция с типом bigint, он же int8;
• входные параметры тут же берутся по модулю во избежание;
• функция помечена как IMMUTABLE, что облегчает жизнь оптимизатору, так как это значит, что на одинаковых входных данных будет возвращен тот же результат;
• функция помечена как STRICT, что означает результат NULL, если хотя бы один из аргументов NULL.

В результате всего этого добра хватило для того, чтобы творение рук моих было увековечено в wiki.postgresql.org.

Если сей опус будет встречен с пониманием, то для него существует продолжение о том, как расчитать НОК (Наименьшее Общее Кратное).