From: Vik Fearing <vik.fearing@2ndquadrant.com>
Subject: Greatest Common Divisor
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Message-ID: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
Date: Sat, 28 Dec 2019 17:58:52 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.2.2
MIME-Version: 1.0
Content-Type: multipart/mixed;
 boundary="------------A4229E325B4C69FF36A1DB1C"
Content-Language: en-US
Precedence: bulk

This is a multi-part message in MIME format.
--------------A4229E325B4C69FF36A1DB1C
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit

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


--------------A4229E325B4C69FF36A1DB1C
Content-Type: text/x-patch; charset=UTF-8;
 name="gcd.0001.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="gcd.0001.patch"

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

--------------A4229E325B4C69FF36A1DB1C--