"Euclide taxis" or "CAL NOD using PostgreSQL"

Someone David Fetter wrote a post about how to calculate the GCD (Greatest Common Divider, not the brotherhood of the same name) of two numbers using PostgreSQL . And he called it the “fast way.”

WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .

1. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
2. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
3. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
4. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
5. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
6. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
7. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .
8. WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .

WITH RECURSIVE t(a, b) AS ( VALUES (38, 12) UNION ALL SELECT least(a, b), abs(a - b) FROM t WHERE abs(a - b) > 0 ) SELECT a AS gcd FROM t WHERE a = b; * This source code was highlighted with Source Code Highlighter .

')
However, my hot nature, honestly spent 5 years at the university, wanted not to agree. From this, in fact, began my research.

For a start, a really quick version

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 particular example, we find the gcd (38, 12), which is 2.

To refine and facilitate further 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:

• the function works with the bigint type, it is int8;
• input parameters are immediately taken to avoid the module;
• 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 goodness was enough for the creation of my hands 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 Common Multiple).