I recently came across the need for a gcd function (actually I needed lcm) and was surprised that we didn't have one.
So here one is, using the basic Euclidean algorithm. I made one for smallint, integer, and bigint. -- Vik Fearing +33 6 46 75 15 36 http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml index 57a1539506..b2c663cd92 100644 --- a/doc/src/sgml/func.sgml +++ b/doc/src/sgml/func.sgml @@ -870,6 +870,19 @@ <entry><literal>-43</literal></entry> </row> + <row> + <entry> + <indexterm> + <primary>gcd</primary> + </indexterm> + <literal><function>gcd(<replaceable>a</replaceable>, <replaceable>b</replaceable>)</function></literal> + </entry> + <entry>(same as argument types)</entry> + <entry>greatest common divisor</entry> + <entry><literal>gcd(1071, 462)</literal></entry> + <entry><literal>21</literal></entry> + </row> + <row> <entry> <indexterm> diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c index 04825fc77d..bc74d367bb 100644 --- a/src/backend/utils/adt/int.c +++ b/src/backend/utils/adt/int.c @@ -1196,6 +1196,47 @@ int2abs(PG_FUNCTION_ARGS) PG_RETURN_INT16(result); } +/* int[24]gcd() + * Greatest Common Divisor + */ +Datum +int4gcd(PG_FUNCTION_ARGS) +{ + int32 arg1 = PG_GETARG_INT32(0); + int32 arg2 = PG_GETARG_INT32(1); + + while (arg2 != 0) + { + int32 tmp = arg2; + arg2 = arg1 % arg2; + arg1 = tmp; + } + + if (arg1 < 0) + arg1 = -arg1; + + PG_RETURN_INT32(arg1); +} + +Datum +int2gcd(PG_FUNCTION_ARGS) +{ + int16 arg1 = PG_GETARG_INT16(0); + int16 arg2 = PG_GETARG_INT16(1); + + while (arg2 != 0) + { + int16 tmp = arg2; + arg2 = arg1 % arg2; + arg1 = tmp; + } + + if (arg1 < 0) + arg1 = -arg1; + + PG_RETURN_INT16(arg1); +} + Datum int2larger(PG_FUNCTION_ARGS) { diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c index a40ae40dff..97cbd1443b 100644 --- a/src/backend/utils/adt/int8.c +++ b/src/backend/utils/adt/int8.c @@ -667,6 +667,28 @@ int8mod(PG_FUNCTION_ARGS) PG_RETURN_INT64(arg1 % arg2); } +/* int8gcd() + * Greatest Common Divisor + */ +Datum +int8gcd(PG_FUNCTION_ARGS) +{ + int64 arg1 = PG_GETARG_INT64(0); + int64 arg2 = PG_GETARG_INT64(1); + + while (arg2 != 0) + { + int64 tmp = arg2; + arg2 = arg1 % arg2; + arg1 = tmp; + } + + if (arg1 < 0) + arg1 = -arg1; + + PG_RETURN_INT64(arg1); +} + Datum int8inc(PG_FUNCTION_ARGS) diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index ac8f64b219..b3057f2cdd 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -10729,4 +10729,15 @@ proname => 'pg_partition_root', prorettype => 'regclass', proargtypes => 'regclass', prosrc => 'pg_partition_root' }, +# greatest common divisor +{ oid => '8463', descr => 'greatest common divisor', + proname => 'gcd', prorettype => 'int2', proargtypes => 'int2 int2', + prosrc => 'int2gcd' }, +{ oid => '8464', descr => 'greatest common divisor', + proname => 'gcd', prorettype => 'int4', proargtypes => 'int4 int4', + prosrc => 'int4gcd' }, +{ oid => '8465', descr => 'greatest common divisor', + proname => 'gcd', prorettype => 'int8', proargtypes => 'int8 int8', + prosrc => 'int8gcd' }, + ] diff --git a/src/test/regress/expected/int2.out b/src/test/regress/expected/int2.out index 8c255b9e4d..66906a7b03 100644 --- a/src/test/regress/expected/int2.out +++ b/src/test/regress/expected/int2.out @@ -306,3 +306,11 @@ FROM (VALUES (-2.5::numeric), 2.5 | 3 (7 rows) +-- gcd +SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b) +FROM (VALUES (24948, 4914)) AS v(a, b); + gcd | gcd | gcd | gcd +-----+-----+-----+----- + 378 | 378 | 378 | 378 +(1 row) + diff --git a/src/test/regress/expected/int4.out b/src/test/regress/expected/int4.out index bda7a8daef..a261964454 100644 --- a/src/test/regress/expected/int4.out +++ b/src/test/regress/expected/int4.out @@ -403,3 +403,11 @@ FROM (VALUES (-2.5::numeric), 2.5 | 3 (7 rows) +-- gcd +SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b) +FROM (VALUES (61866666, 6410818)) AS v(a, b); + gcd | gcd | gcd | gcd +------+------+------+------ + 1466 | 1466 | 1466 | 1466 +(1 row) + diff --git a/src/test/regress/expected/int8.out b/src/test/regress/expected/int8.out index 8447a28c3d..1a0836998a 100644 --- a/src/test/regress/expected/int8.out +++ b/src/test/regress/expected/int8.out @@ -388,6 +388,16 @@ SELECT '' AS five, q1 * 2 AS "twice int4" FROM INT8_TBL; | 9135780246913578 (5 rows) +SELECT q1, q2, gcd(q1, q2) FROM INT8_TBL; + q1 | q2 | gcd +------------------+-------------------+------------------ + 123 | 456 | 3 + 123 | 4567890123456789 | 3 + 4567890123456789 | 123 | 3 + 4567890123456789 | 4567890123456789 | 4567890123456789 + 4567890123456789 | -4567890123456789 | 4567890123456789 +(5 rows) + -- int8 op int4 SELECT q1 + 42::int4 AS "8plus4", q1 - 42::int4 AS "8minus4", q1 * 42::int4 AS "8mul4", q1 / 42::int4 AS "8div4" FROM INT8_TBL; 8plus4 | 8minus4 | 8mul4 | 8div4 diff --git a/src/test/regress/sql/int2.sql b/src/test/regress/sql/int2.sql index 7dbafb6dac..e0bf7276fc 100644 --- a/src/test/regress/sql/int2.sql +++ b/src/test/regress/sql/int2.sql @@ -112,3 +112,7 @@ FROM (VALUES (-2.5::numeric), (0.5::numeric), (1.5::numeric), (2.5::numeric)) t(x); + +-- gcd +SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b) +FROM (VALUES (24948, 4914)) AS v(a, b); diff --git a/src/test/regress/sql/int4.sql b/src/test/regress/sql/int4.sql index f014cb2d32..0acc6c9060 100644 --- a/src/test/regress/sql/int4.sql +++ b/src/test/regress/sql/int4.sql @@ -155,3 +155,7 @@ FROM (VALUES (-2.5::numeric), (0.5::numeric), (1.5::numeric), (2.5::numeric)) t(x); + +-- gcd +SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b) +FROM (VALUES (61866666, 6410818)) AS v(a, b); diff --git a/src/test/regress/sql/int8.sql b/src/test/regress/sql/int8.sql index e890452236..76959270e0 100644 --- a/src/test/regress/sql/int8.sql +++ b/src/test/regress/sql/int8.sql @@ -79,6 +79,8 @@ SELECT 37 - q1 AS minus4 FROM INT8_TBL; SELECT '' AS five, 2 * q1 AS "twice int4" FROM INT8_TBL; SELECT '' AS five, q1 * 2 AS "twice int4" FROM INT8_TBL; +SELECT q1, q2, gcd(q1, q2) FROM INT8_TBL; + -- int8 op int4 SELECT q1 + 42::int4 AS "8plus4", q1 - 42::int4 AS "8minus4", q1 * 42::int4 AS "8mul4", q1 / 42::int4 AS "8div4" FROM INT8_TBL; -- int4 op int8