"Euclid steers" or "Counting GCD using PostgreSQL"

Somehow, someone David Fetter wrote a post on how to calculate the GCD (Greatest Common Divisor, not the brotherhood of the same name) of two numbers using PostgreSQL . And he called it the "quick way."

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.

However, my ardent nature, who had honestly sat for 5 years at the university, wished to disagree. From this, in fact, my research began.

For starters, a really quick option:

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.

I am sure that many will recognize the famous Euclidean algorithm in this implementation. In this specific example, we find the GCD (38, 12), which is 2.

To ennoble and facilitate the future use of this miracle, it was decided to write a function:

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.

Please pay attention to some improvements:

• function with type bigint works, it is int8;
• input parameters are taken modulo immediately to avoid;
• the function is marked as IMMUTABLE, which makes life easier for the optimizer, since this means that the same result will be returned on the same input data;
• the function is marked as STRICT, which means the result is NULL if at least one of the arguments is NULL.

As a result of all this, good was enough for my handiwork to be immortalized in wiki.postgresql.org .

If this opus is met with understanding, then for him there is a continuation on how to calculate the NOC (Least General Multiple).