Re: Greatest Common Divisor

Vik Fearing <[email protected]>
Newsgroups gmane.comp.db.postgresql.devel.general
Message-ID <[email protected]> 
On 02/01/2020 16:12, Tom Lane wrote:
> Stephen Frost <[email protected]> writes:
>> * Dean Rasheed ([email protected]) wrote:
>>> I'm not objecting to adding it, I'm just curious. In fact, I think
>>> that if we do add this, then we should probably add lcm() at the same
>>> time, since handling its overflow cases is sufficiently non-trivial to
>>> justify not requiring users to have to implement it themselves.
>> I tend to agree with this.
> Does this impact the decision about whether we need a variant for
> numeric?  I was leaning against that, primarily because (a)
> it'd introduce a set of questions about what to do with non-integral
> inputs, and (b) it'd make the patch quite a lot larger, I imagine.
> But a variant of lcm() that returns numeric would have much more
> resistance to overflow.
>
> Maybe we could just define "lcm(bigint, bigint) returns numeric"
> and figure that that covers all cases, but it feels slightly
> weird.  You couldn't do lcm(lcm(a,b),c) without casting.
> I guess that particular use-case could be addressed with
> "lcm(variadic bigint[]) returns numeric", but that's getting
> really odd.


Okay.  Here is a version that should handle everyone's comments.


gcd() is now strictly positive, so INT_MIN is no longer a valid result.


I added an lcm() function. It returns the same type as its arguments so
overflow is possible.  I made this choice because int2mul returns int2
(and same for its friends).  One can just cast to a bigger integer if
needed.


Because of that, I added a version of gcd() and lcm() for numeric.  This
was my first time working with numeric so reviewers should pay extra
attention there, please.


Patch attached.

-- 

Vik Fearing
gcd.0004.patch (text/x-patch, 23.2 KB) 
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 57a1539506..e2b7d6d240 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -870,6 +870,32 @@
        <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>
+         <primary>lcm</primary>
+        </indexterm>
+        <literal><function>lcm(<replaceable>a</replaceable>, <replaceable>b</replaceable>)</function></literal>
+       </entry>
+       <entry>(same as argument types)</entry>
+       <entry>least common multiple</entry>
+       <entry><literal>lcm(1071, 462)</literal></entry>
+       <entry><literal>23562</literal></entry>
+      </row>
+
       <row>
        <entry>
         <indexterm>
diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c
index 583ce71e66..a70009ae09 100644
--- a/src/backend/utils/adt/int.c
+++ b/src/backend/utils/adt/int.c
@@ -1196,6 +1196,199 @@ int2abs(PG_FUNCTION_ARGS)
 	PG_RETURN_INT16(result);
 }
 
+/*
+ * Greatest Common Divisor
+ *
+ * Special cases:
+ *   - gcd(x, 0) = x; because 0 is divisible by anything
+ *   - gcd(0, 0) = 0; complies with the previous definition and is a
+ *                    common convention
+ *
+ * The following cases involving INT_MIN have two possible results.  They could
+ * return INT_MIN because INT_MIN is a valid divisor of INT_MIN, or they could
+ * throw an exception because the result is negative.
+ * The consensus is to throw an exception.
+ *
+ *   - gcd(INT_MIN, 0)
+ *   - gcd(INT_MIN, INT_MIN)
+ *
+ * Any other value with INT_MIN will be a positive value representable within
+ * the data type.
+ */
+static int32
+int4gcd_internal(int32 arg1, int32 arg2)
+{
+	int32	swap;
+
+	/*
+	 * Put the greater value in arg1.
+	 * This would happen automatically in the loop below, but avoids an
+	 * expensive modulo simulation on some architectures.
+	 */
+	if (arg1 < arg2)
+	{
+		swap = arg1;
+		arg1 = arg2;
+		arg2 = swap;
+	}
+
+	/* Special care needs to be taken with INT_MIN.  See comments above. */
+	if (arg2 == PG_INT32_MIN)
+	{
+		if (arg1 == 0 || arg1 == PG_INT32_MIN)
+			ereport(ERROR,
+					(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+					 errmsg("integer out of range")));
+		arg1 = -arg1;
+	}
+
+	/* Find GCD using the basic Euclidean algorithm */
+	while (arg2 != 0)
+	{
+		swap = arg2;
+		arg2 = arg1 % arg2;
+		arg1 = swap;
+	}
+
+	/*
+	 * Make sure the result is positive. (We know we don't have INT_MIN
+	 * anymore).
+	 */
+	if (arg1 < 0)
+		arg1 = -arg1;
+
+	return arg1;
+}
+
+static int16
+int2gcd_internal(int16 arg1, int16 arg2)
+{
+	/* See int4gcd_internal for commented version. */
+	int16	swap;
+
+	if (arg1 < arg2)
+	{
+		swap = arg1;
+		arg1 = arg2;
+		arg2 = swap;
+	}
+
+	if (arg2 == PG_INT16_MIN)
+	{
+		if (arg1 == 0 || arg1 == PG_INT16_MIN)
+			ereport(ERROR,
+					(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+					 errmsg("smallint out of range")));
+		arg1 = -arg1;
+	}
+
+	while (arg2 != 0)
+	{
+		swap = arg2;
+		arg2 = arg1 % arg2;
+		arg1 = swap;
+	}
+
+	if (arg1 < 0)
+		arg1 = -arg1;
+
+	return arg1;
+}
+
+Datum
+int4gcd(PG_FUNCTION_ARGS)
+{
+	int32	arg1 = PG_GETARG_INT32(0);
+	int32	arg2 = PG_GETARG_INT32(1);
+	int32	result;
+
+	result = int4gcd_internal(arg1, arg2);
+
+	PG_RETURN_INT32(result);
+}
+
+Datum
+int2gcd(PG_FUNCTION_ARGS)
+{
+	int16	arg1 = PG_GETARG_INT16(0);
+	int16	arg2 = PG_GETARG_INT16(1);
+	int16	result;
+
+	result = int2gcd_internal(arg1, arg2);
+
+	PG_RETURN_INT16(result);
+}
+
+/*
+ * Least Common Multiple
+ *
+ * Both arguments must be positive.  If either argument is 0 we can just return
+ * 0 without further calculation.  This has the nice side effect of avoiding a
+ * division by zero for lcm(0, 0) since we use gcd in the formula.  Also, if
+ * both arguments are the same, we can just return it without further
+ * calculation.
+ */
+
+Datum
+int4lcm(PG_FUNCTION_ARGS)
+{
+	int32	arg1 = PG_GETARG_INT32(0);
+	int32	arg2 = PG_GETARG_INT32(1);
+	int32	gcd;
+	int32	result;
+
+	if (arg1 < 0 || arg2 < 0)
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("integer out of range")));
+
+	if (arg1 == 0 || arg2 == 0)
+		PG_RETURN_INT32(0);
+
+	if (arg1 == arg2)
+		PG_RETURN_INT32(arg1);
+
+	gcd = int4gcd_internal(arg1, arg2);
+	arg1 = arg1 / gcd;
+
+	if (unlikely(pg_mul_s32_overflow(arg1, arg2, &result)))
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("integer out of range")));
+
+	PG_RETURN_INT32(result);
+}
+
+Datum
+int2lcm(PG_FUNCTION_ARGS)
+{
+	int16	arg1 = PG_GETARG_INT16(0);
+	int16	arg2 = PG_GETARG_INT16(1);
+	int16	gcd;
+	int16	result;
+
+	if (arg1 < 0 || arg2 < 0)
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("smallint out of range")));
+
+	if (arg1 == 0 || arg2 == 0)
+		PG_RETURN_INT16(0);
+
+	if (arg1 == arg2)
+		PG_RETURN_INT16(arg1);
+
+	gcd = int2gcd_internal(arg1, arg2);
+	arg1 = arg1 / gcd;
+
+	if (unlikely(pg_mul_s16_overflow(arg1, arg2, &result)))
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("smallint out of range")));
+
+	PG_RETURN_INT16(result);
+}
+
 Datum
 int2larger(PG_FUNCTION_ARGS)
 {
diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c
index fcdf77331e..7344dedb96 100644
--- a/src/backend/utils/adt/int8.c
+++ b/src/backend/utils/adt/int8.c
@@ -667,6 +667,94 @@ int8mod(PG_FUNCTION_ARGS)
 	PG_RETURN_INT64(arg1 % arg2);
 }
 
+/*
+ * Greatest Common Divisor
+ *
+ * See int4gcd_internal for commented version.
+ */
+
+static int64
+int8gcd_internal(int64 arg1, int64 arg2)
+{
+	int64	swap;
+
+	if (arg1 < arg2)
+	{
+		swap = arg1;
+		arg1 = arg2;
+		arg2 = swap;
+	}
+
+	if (arg2 == PG_INT64_MIN)
+	{
+		if (arg1 == 0 || arg1 == PG_INT64_MIN)
+			ereport(ERROR,
+					(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+					 errmsg("bigint out of range")));
+		arg1 = -arg1;
+	}
+
+	while (arg2 != 0)
+	{
+		swap = arg2;
+		arg2 = arg1 % arg2;
+		arg1 = swap;
+	}
+
+	if (arg1 < 0)
+		arg1 = -arg1;
+
+	return arg1;
+}
+
+Datum
+int8gcd(PG_FUNCTION_ARGS)
+{
+	int64	arg1 = PG_GETARG_INT64(0);
+	int64	arg2 = PG_GETARG_INT64(1);
+	int64	result;
+
+	result = int8gcd_internal(arg1, arg2);
+
+	PG_RETURN_INT64(result);
+}
+
+/*
+ * Least Common Multiple
+ *
+ * See comments for int[24]lcm in int.c
+ */
+
+Datum
+int8lcm(PG_FUNCTION_ARGS)
+{
+	int64	arg1 = PG_GETARG_INT64(0);
+	int64	arg2 = PG_GETARG_INT64(1);
+	int64	gcd;
+	int64	result;
+
+	if (arg1 < 0 || arg2 < 0)
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("bigint out of range")));
+
+	if (arg1 == 0 || arg2 == 0)
+		PG_RETURN_INT64(0);
+
+	if (arg1 == arg2)
+		PG_RETURN_INT64(arg1);
+
+	gcd = int8gcd_internal(arg1, arg2);
+	arg1 = arg1 / gcd;
+
+	if (unlikely(pg_mul_s64_overflow(arg1, arg2, &result)))
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("bigint out of range")));
+
+	PG_RETURN_INT64(result);
+}
+
 
 Datum
 int8inc(PG_FUNCTION_ARGS)
diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index 14054272c8..dfee1012b0 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -220,6 +220,8 @@ struct NumericData
 	 | ((n)->choice.n_short.n_header & NUMERIC_SHORT_WEIGHT_MASK)) \
 	: ((n)->choice.n_long.n_weight))
 
+#define NUMERIC_IS_INTEGRAL(n)	(NUMERIC_NDIGITS(n) <= (NUMERIC_WEIGHT(n) + 1))
+
 /* ----------
  * NumericVar is the format we use for arithmetic.  The digit-array part
  * is the same as the NumericData storage format, but the header is more
@@ -2691,6 +2693,143 @@ numeric_div_trunc(PG_FUNCTION_ARGS)
 }
 
 
+/*
+ * Greatest Common Divisor
+ *
+ * We define here that gcd(n, 0) = n and therefore gdc(0, 0) = 0.
+ * See the comments on int[24]gcd for more details.
+ */
+static void
+gcd_var(NumericVar arg1, NumericVar arg2, NumericVar *result)
+{
+	NumericVar	swap;
+	int			cmp;
+
+	/*
+	 * Unlike the integer types, there are no negative numerics that cannot be
+	 * represented positively, so just abs them from the beginning.
+	 */
+	arg1.sign = NUMERIC_POS;
+	arg2.sign = NUMERIC_POS;
+
+	/* gcd(a, a) = a */
+	cmp = cmp_var(&arg1, &arg2);
+	if (cmp == 0)
+	{
+		set_var_from_var(&arg1, result);
+		return;
+	}
+
+	init_var(&swap);
+
+	/* Save ourselves a call to mod_var if arg1 < arg2 */
+	if (cmp == -1)
+	{
+		set_var_from_var(&arg1, &swap);
+		set_var_from_var(&arg2, &arg1);
+		set_var_from_var(&swap, &arg2);
+	}
+
+	/* Use basic Euclidean algorithm for GCD */
+	while (arg2.ndigits != 0)
+	{
+		mod_var(&arg1, &arg2, &swap);
+		set_var_from_var(&arg2, &arg1);
+		set_var_from_var(&swap, &arg2);
+	}
+
+	free_var(&swap);
+
+	set_var_from_var(&arg1, result);
+}
+
+Datum
+numeric_gcd(PG_FUNCTION_ARGS)
+{
+	Numeric		num1 = PG_GETARG_NUMERIC(0);
+	Numeric		num2 = PG_GETARG_NUMERIC(1);
+	Numeric		res;
+	NumericVar	arg1;
+	NumericVar	arg2;
+	NumericVar	result;
+
+	if (NUMERIC_IS_NAN(num1) || NUMERIC_IS_NAN(num2))
+		PG_RETURN_NUMERIC(make_result(&const_nan));
+
+	if (!NUMERIC_IS_INTEGRAL(num1) || !NUMERIC_IS_INTEGRAL(num2))
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+				 errmsg("parameters to gcd must be integral")));
+
+	init_var_from_num(num1, &arg1);
+	init_var_from_num(num2, &arg2);
+
+	init_var(&result);
+
+	gcd_var(arg1, arg2, &result);
+	trunc_var(&result, 0);
+	res = make_result_opt_error(&result, NULL);
+
+	free_var(&result);
+
+	PG_RETURN_NUMERIC(res);
+}
+
+/*
+ * Least Common Multiple
+ */
+
+Datum
+numeric_lcm(PG_FUNCTION_ARGS)
+{
+	Numeric		num1 = PG_GETARG_NUMERIC(0);
+	Numeric		num2 = PG_GETARG_NUMERIC(1);
+	Numeric		res;
+	NumericVar	arg1;
+	NumericVar	arg2;
+	NumericVar	result;
+
+	/* If we get a NaN, just return NaN */
+	if (NUMERIC_IS_NAN(num1) || NUMERIC_IS_NAN(num2))
+		PG_RETURN_NUMERIC(make_result(&const_nan));
+
+	/* Values must be integral */
+	if (!NUMERIC_IS_INTEGRAL(num1) || !NUMERIC_IS_INTEGRAL(num2))
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+				 errmsg("parameters to lcm must be integral")));
+
+	/* Values must be positive */
+	if (NUMERIC_SIGN(num1) == NUMERIC_NEG || NUMERIC_SIGN(num2) == NUMERIC_NEG)
+		ereport(ERROR,
+				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+				 errmsg("numeric out of range")));
+
+	/* If either argument is 0, the result is 0 */
+	if (NUMERIC_NDIGITS(num1) == 0 || NUMERIC_NDIGITS(num2) == 0)
+		PG_RETURN_NUMERIC(make_result(&const_zero));
+
+	init_var_from_num(num1, &arg1);
+	init_var_from_num(num2, &arg2);
+
+	/* If both arguments are the same, just return it */
+	if (cmp_var(&arg1, &arg2) == 0)
+		PG_RETURN_NUMERIC(num1);
+
+	init_var(&result);
+
+	/* result = arg1 / gcd(arg1, arg2) * arg2 */
+	gcd_var(arg1, arg2, &result);
+	div_var(&arg1, &result, &result, 0, false);
+	mul_var(&arg2, &result, &result, 0);
+
+	res = make_result_opt_error(&result, NULL);
+
+	free_var(&result);
+
+	PG_RETURN_NUMERIC(res);
+}
+
 /*
  * numeric_mod() -
  *
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 0b6045acb1..334fe30d44 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -10729,4 +10729,32 @@
   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' },
+{ oid => '8466', descr => 'greatest common divisor',
+  proname => 'gcd', prorettype => 'numeric', proargtypes => 'numeric numeric',
+  prosrc => 'numeric_gcd' },
+
+# least common multiple
+{ oid => '8467', descr => 'least common multiple',
+  proname => 'lcm', prorettype => 'int2', proargtypes => 'int2 int2',
+  prosrc => 'int2lcm' },
+{ oid => '8468', descr => 'least common multiple',
+  proname => 'lcm', prorettype => 'int4', proargtypes => 'int4 int4',
+  prosrc => 'int4lcm' },
+{ oid => '8469', descr => 'least common multiple',
+  proname => 'lcm', prorettype => 'int8', proargtypes => 'int8 int8',
+  prosrc => 'int8lcm' },
+{ oid => '8470', descr => 'least common multiple',
+  proname => 'lcm', prorettype => 'numeric', proargtypes => 'numeric numeric',
+  prosrc => 'numeric_lcm' },
+
 ]
diff --git a/src/test/regress/expected/int2.out b/src/test/regress/expected/int2.out
index 8c255b9e4d..17ad285245 100644
--- a/src/test/regress/expected/int2.out
+++ b/src/test/regress/expected/int2.out
@@ -306,3 +306,65 @@ FROM (VALUES (-2.5::numeric),
   2.5 |          3
 (7 rows)
 
+-- gcd
+SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b), gcd(b, a)
+FROM (VALUES (24948::int2, 4914::int2)) AS v(a, b);
+ gcd | gcd | gcd | gcd | gcd 
+-----+-----+-----+-----+-----
+ 378 | 378 | 378 | 378 | 378
+(1 row)
+
+SELECT gcd((-32768)::int2, 16384::int2);
+  gcd  
+-------
+ 16384
+(1 row)
+
+SELECT gcd((-32768)::int2, (-1)::int2);
+ gcd 
+-----
+   1
+(1 row)
+
+SELECT gcd((-32768)::int2, 0::int2); -- fail
+ERROR:  smallint out of range
+SELECT gcd((-32768)::int2, (-32768)::int2); -- fail
+ERROR:  smallint out of range
+-- lcm
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::int2, 462::int2)) AS v(a, b);
+ lcm  | lcm  
+------+------
+ 2310 | 2310
+(1 row)
+
+SELECT lcm(42::int2, 42::int2);
+ lcm 
+-----
+  42
+(1 row)
+
+SELECT lcm(42::int2, 0::int2);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::int2, 42::int2);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::int2, 0::int2);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm((-32768)::int2, 0::int2); -- fail
+ERROR:  smallint out of range
+SELECT lcm(0::int2, (-32768)::int2); -- fail
+ERROR:  smallint out of range
+SELECT lcm(32767::int2, 32766::int2); -- fail
+ERROR:  smallint out of range
diff --git a/src/test/regress/expected/int4.out b/src/test/regress/expected/int4.out
index bda7a8daef..a2ad10f60f 100644
--- a/src/test/regress/expected/int4.out
+++ b/src/test/regress/expected/int4.out
@@ -403,3 +403,65 @@ FROM (VALUES (-2.5::numeric),
   2.5 |          3
 (7 rows)
 
+-- gcd
+SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b), gcd(b, a)
+FROM (VALUES (61866666::int4, 6410818::int4)) AS v(a, b);
+ gcd  | gcd  | gcd  | gcd  | gcd  
+------+------+------+------+------
+ 1466 | 1466 | 1466 | 1466 | 1466
+(1 row)
+
+SELECT gcd((-2147483648)::int4, 1073741824::int4);
+    gcd     
+------------
+ 1073741824
+(1 row)
+
+SELECT gcd((-2147483648)::int4, (-1)::int4);
+ gcd 
+-----
+   1
+(1 row)
+
+SELECT gcd((-2147483648)::int4, 0::int4); -- fail
+ERROR:  integer out of range
+SELECT gcd((-2147483648)::int4, (-2147483648)::int4); -- fail
+ERROR:  integer out of range
+-- lcm
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::int4, 462::int4)) AS v(a, b);
+ lcm  | lcm  
+------+------
+ 2310 | 2310
+(1 row)
+
+SELECT lcm(42::int4, 42::int4);
+ lcm 
+-----
+  42
+(1 row)
+
+SELECT lcm(42::int4, 0::int4);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::int4, 42::int4);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::int4, 0::int4);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm((-2147483648)::int4, 0::int4); -- fail
+ERROR:  integer out of range
+SELECT lcm(0::int4, (-2147483648)::int4); -- fail
+ERROR:  integer out of range
+SELECT lcm(2147483647::int4, 2147483646::int4); -- fail
+ERROR:  integer out of range
diff --git a/src/test/regress/expected/int8.out b/src/test/regress/expected/int8.out
index 8447a28c3d..51c1007d86 100644
--- a/src/test/regress/expected/int8.out
+++ b/src/test/regress/expected/int8.out
@@ -886,3 +886,65 @@ FROM (VALUES (-2.5::numeric),
   2.5 |          3
 (7 rows)
 
+-- gcd
+SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b), gcd(b, a)
+FROM (VALUES (288484263558::int8, 29893644334::int8)) AS v(a, b);
+   gcd   |   gcd   |   gcd   |   gcd   |   gcd   
+---------+---------+---------+---------+---------
+ 6835958 | 6835958 | 6835958 | 6835958 | 6835958
+(1 row)
+
+SELECT gcd((-9223372036854775808)::int8, 4611686018427387904::int8);
+         gcd         
+---------------------
+ 4611686018427387904
+(1 row)
+
+SELECT gcd((-9223372036854775808)::int8, (-1)::int8);
+ gcd 
+-----
+   1
+(1 row)
+
+SELECT gcd((-9223372036854775808)::int8, 0::int8); -- fail
+ERROR:  bigint out of range
+SELECT gcd((-9223372036854775808)::int8, (-9223372036854775808)::int8); -- fail
+ERROR:  bigint out of range
+-- lcm
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::int8, 462::int8)) AS v(a, b);
+ lcm  | lcm  
+------+------
+ 2310 | 2310
+(1 row)
+
+SELECT lcm(42::int8, 42::int8);
+ lcm 
+-----
+  42
+(1 row)
+
+SELECT lcm(42::int8, 0::int8);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::int8, 42::int8);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::int8, 0::int8);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm((-9223372036854775808)::int8, 0::int8); -- fail
+ERROR:  bigint out of range
+SELECT lcm(0::int8, (-9223372036854775808)::int8); -- fail
+ERROR:  bigint out of range
+SELECT lcm(9223372036854775807::int8, 9223372036854775806::int8); -- fail
+ERROR:  bigint out of range
diff --git a/src/test/regress/expected/numeric.out b/src/test/regress/expected/numeric.out
index 1cb3c3bfab..0ac9100e5b 100644
--- a/src/test/regress/expected/numeric.out
+++ b/src/test/regress/expected/numeric.out
@@ -2094,3 +2094,64 @@ SELECT SUM((-9999)::numeric) FROM generate_series(1, 100000);
  -999900000
 (1 row)
 
+--
+-- Tests for GCD()
+--
+SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b), gcd(b, a)
+FROM (VALUES (330::numeric, 462::numeric), (330.000::numeric, 462.000::numeric)) AS v(a, b);
+ gcd | gcd | gcd | gcd | gcd 
+-----+-----+-----+-----+-----
+  66 |  66 |  66 |  66 |  66
+  66 |  66 |  66 |  66 |  66
+(2 rows)
+
+SELECT gcd(0::numeric, 0::numeric);
+ gcd 
+-----
+   0
+(1 row)
+
+SELECT gcd(330.3::numeric, 462::numeric); -- fails
+ERROR:  parameters to gcd must be integral
+SELECT gcd(330::numeric, 462.5::numeric); -- fails
+ERROR:  parameters to gcd must be integral
+--
+-- Tests for LCM()
+--
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::numeric, 462::numeric)) AS v(a, b);
+ lcm  | lcm  
+------+------
+ 2310 | 2310
+(1 row)
+
+SELECT lcm(42::numeric, 42::numeric);
+ lcm 
+-----
+  42
+(1 row)
+
+SELECT lcm(42::numeric, 0::numeric);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::numeric, 42::numeric);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(0::numeric, 0::numeric);
+ lcm 
+-----
+   0
+(1 row)
+
+SELECT lcm(330.3::numeric, 462::numeric); -- fails
+ERROR:  parameters to lcm must be integral
+SELECT lcm(330::numeric, 462.5::numeric); -- fails
+ERROR:  parameters to lcm must be integral
+SELECT lcm(9999 * (10::numeric)^131068 + (10::numeric^131068 - 1), 2); -- fails
+ERROR:  value overflows numeric format
diff --git a/src/test/regress/sql/int2.sql b/src/test/regress/sql/int2.sql
index 7dbafb6dac..2c714d0bcf 100644
--- a/src/test/regress/sql/int2.sql
+++ b/src/test/regress/sql/int2.sql
@@ -112,3 +112,22 @@ 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), gcd(b, a)
+FROM (VALUES (24948::int2, 4914::int2)) AS v(a, b);
+SELECT gcd((-32768)::int2, 16384::int2);
+SELECT gcd((-32768)::int2, (-1)::int2);
+SELECT gcd((-32768)::int2, 0::int2); -- fail
+SELECT gcd((-32768)::int2, (-32768)::int2); -- fail
+
+-- lcm
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::int2, 462::int2)) AS v(a, b);
+SELECT lcm(42::int2, 42::int2);
+SELECT lcm(42::int2, 0::int2);
+SELECT lcm(0::int2, 42::int2);
+SELECT lcm(0::int2, 0::int2);
+SELECT lcm((-32768)::int2, 0::int2); -- fail
+SELECT lcm(0::int2, (-32768)::int2); -- fail
+SELECT lcm(32767::int2, 32766::int2); -- fail
diff --git a/src/test/regress/sql/int4.sql b/src/test/regress/sql/int4.sql
index f014cb2d32..d88edf8f1f 100644
--- a/src/test/regress/sql/int4.sql
+++ b/src/test/regress/sql/int4.sql
@@ -155,3 +155,22 @@ 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), gcd(b, a)
+FROM (VALUES (61866666::int4, 6410818::int4)) AS v(a, b);
+SELECT gcd((-2147483648)::int4, 1073741824::int4);
+SELECT gcd((-2147483648)::int4, (-1)::int4);
+SELECT gcd((-2147483648)::int4, 0::int4); -- fail
+SELECT gcd((-2147483648)::int4, (-2147483648)::int4); -- fail
+
+-- lcm
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::int4, 462::int4)) AS v(a, b);
+SELECT lcm(42::int4, 42::int4);
+SELECT lcm(42::int4, 0::int4);
+SELECT lcm(0::int4, 42::int4);
+SELECT lcm(0::int4, 0::int4);
+SELECT lcm((-2147483648)::int4, 0::int4); -- fail
+SELECT lcm(0::int4, (-2147483648)::int4); -- fail
+SELECT lcm(2147483647::int4, 2147483646::int4); -- fail
diff --git a/src/test/regress/sql/int8.sql b/src/test/regress/sql/int8.sql
index e890452236..2ced94ec0a 100644
--- a/src/test/regress/sql/int8.sql
+++ b/src/test/regress/sql/int8.sql
@@ -225,3 +225,22 @@ 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), gcd(b, a)
+FROM (VALUES (288484263558::int8, 29893644334::int8)) AS v(a, b);
+SELECT gcd((-9223372036854775808)::int8, 4611686018427387904::int8);
+SELECT gcd((-9223372036854775808)::int8, (-1)::int8);
+SELECT gcd((-9223372036854775808)::int8, 0::int8); -- fail
+SELECT gcd((-9223372036854775808)::int8, (-9223372036854775808)::int8); -- fail
+
+-- lcm
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::int8, 462::int8)) AS v(a, b);
+SELECT lcm(42::int8, 42::int8);
+SELECT lcm(42::int8, 0::int8);
+SELECT lcm(0::int8, 42::int8);
+SELECT lcm(0::int8, 0::int8);
+SELECT lcm((-9223372036854775808)::int8, 0::int8); -- fail
+SELECT lcm(0::int8, (-9223372036854775808)::int8); -- fail
+SELECT lcm(9223372036854775807::int8, 9223372036854775806::int8); -- fail
diff --git a/src/test/regress/sql/numeric.sql b/src/test/regress/sql/numeric.sql
index a939412359..59b4f856e5 100644
--- a/src/test/regress/sql/numeric.sql
+++ b/src/test/regress/sql/numeric.sql
@@ -1043,3 +1043,25 @@ select scale(-13.000000000000000);
 -- cases that need carry propagation
 SELECT SUM(9999::numeric) FROM generate_series(1, 100000);
 SELECT SUM((-9999)::numeric) FROM generate_series(1, 100000);
+
+--
+-- Tests for GCD()
+--
+SELECT gcd(a, b), gcd(a, -b), gcd(-a, b), gcd(-a, -b), gcd(b, a)
+FROM (VALUES (330::numeric, 462::numeric), (330.000::numeric, 462.000::numeric)) AS v(a, b);
+SELECT gcd(0::numeric, 0::numeric);
+SELECT gcd(330.3::numeric, 462::numeric); -- fails
+SELECT gcd(330::numeric, 462.5::numeric); -- fails
+
+--
+-- Tests for LCM()
+--
+SELECT lcm(a, b), lcm(b, a)
+FROM (VALUES (330::numeric, 462::numeric)) AS v(a, b);
+SELECT lcm(42::numeric, 42::numeric);
+SELECT lcm(42::numeric, 0::numeric);
+SELECT lcm(0::numeric, 42::numeric);
+SELECT lcm(0::numeric, 0::numeric);
+SELECT lcm(330.3::numeric, 462::numeric); -- fails
+SELECT lcm(330::numeric, 462.5::numeric); -- fails
+SELECT lcm(9999 * (10::numeric)^131068 + (10::numeric^131068 - 1), 2); -- fails
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.