"Euclid rules" or "Calculating GCD using PostgreSQL"

that one David Fetter written by post how to calculate NAD (Greatest Common Divisor, not the same brotherhood) of two numbers using the PostgreSQL. Call 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 the

1. )

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, wished to disagree. This, in fact, began my research.

For starters, do a quick version:

WITH RECURSIVE t(a, b) AS (

VALUES (38, 12)

UNION ALL

SELECT b, mod(a,b) FROM t

WHERE b > 0 the

1. )

SELECT a AS gcd FROM t WHERE b = 0;

* This source code was highlighted with Source Code Highlighter.

I'm sure many of you will recognize this implementation of the famous algorithm of Euclid. In this particular example, we find GCD(38, 12), which is equal to 2.

To Refine and facilitate further use of this miracle, decided to write a function:

CREATE OR REPLACE FUNCTION gcd(bigint, bigint) RETURNS bigint AS the

1. $$

WITH RECURSIVE t(a, b) AS (

VALUES (abs($1) :: bigint, abs($2) :: bigint)

UNION ALL

SELECT b, mod(a,b) FROM t

WHERE b > 0 the

2. )

SELECT a AS gcd FROM t WHERE b = 0; the

3. $$

IMMUTABLE

STRICT

LANGUAGE SQL;

* This source code was highlighted with Source Code Highlighter.

Please pay attention to some improvements:
the

the
• function is of type bigint aka int8;
the
• input parameters here are taken modulo in order to avoid;
the
• function is marked as IMMUTABLE, which makes life easier for the optimizer, because it means that the same input will return the same result;
the
• the function is marked STRICT, which means the result is NULL if at least one of the arguments is NULL.

As a result of all of this stuff was enough to ensure that the workmanship of mine own hands was immortalized in wiki.postgresql.org.

If this opus will be met with understanding, for him there is a continuation on how to calculate NOK (Least Common Multiple).

Article based on information from habrahabr.ru