pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: Vik Fearing <vik.fearing@2ndquadrant.com>
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Greatest Common Divisor
Date: Sat, 28 Dec 2019 17:58:52 +0100
Message-ID: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com> (raw )
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
Attachments:
[text/x-patch] gcd.0001.patch (6.3K, ../adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com/2-gcd.0001.patch)
download | inline diff:
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
view thread (70+ messages) latest in thread
Message-ID: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
Permalink: ../adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com/
Also on: postgresql.org/message-id/adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com
copy link · copy postgr.es · copy git am
reply Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: vik.fearing@2ndquadrant.com, pgsql-hackers@lists.postgresql.org
Subject: Re: Greatest Common Divisor
In-Reply-To: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox