From: Vik Fearing <vik.fearing@2ndquadrant.com>
To: Fabien COELHO <coelho@cri.ensmp.fr>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
Date: Sat, 28 Dec 2019 23:03:59 +0100
Message-ID: <dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com> (raw)
In-Reply-To: <alpine.DEB.2.21.1912281848540.24861@pseudo>
References: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
<alpine.DEB.2.21.1912281848540.24861@pseudo>
On 28/12/2019 19:15, Fabien COELHO wrote:
>
>> So here one is, using the basic Euclidean algorithm. I made one for
>> smallint, integer, and bigint.
>
> Should pg provide the LCM as well? Hmmm, probably not, too likely to
> overflow.
I decided against it for that reason.
> Should there be a NUMERIC version as well? I'd say maybe yes.
I thought about that, too, but also decided against it for this patch.
> I'm wondering what it should do on N, 0 and 0, 0. Raise an error?
> Return 0? Return 1? return N? There should be some logic and comments
> explaining it.
Well, gcd(N, 0) is N, and gcd(0, 0) is 0, so I don't see an issue here?
> I'd test with INT_MIN and INT_MAX.
Okay, I'll add tests for those, instead of the pretty much random values
I have now.
> Given that there are no overflows risk with the Euclidian descent, would
> it make sense that the int2 version call the int4 implementation?
Meh.
>
> C modulo operator (%) is a pain because it is not positive remainder
> (2 % -3 == -1 vs 2 % 3 == 2, AFAICR).
This does not seem to be the case...
> It does not seem that fixing the sign afterwards is the right thing to
> do. I'd rather turn both arguments positive before doing the descent.
Why isn't it the right thing to do?
> Which raises an issue with INT_MIN by the way, which has no positive:-(
That's an argument against abs-ing the input values. It's only an issue
with gcd(INT_MIN, INT_MIN) which currently returns INT_MIN. Any other
value with INT_MIN will be 1 or something lower than INT_MAX.
> Also, the usual approach is to exchange args so that the largest is
> first, because there may be a software emulation if the hardware does
> not implement modulo. At least it was the case with some sparc
> processors 25 years ago:-)
The args will exchange themselves.
Thanks for the review! Attached is a new patch that changes the
regression tests based on your comments (and another comment that I got
on irc to test gcd(b, a)).
Attachments:
[text/x-patch] gcd.0002.patch (6.9K, ../dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com/2-gcd.0002.patch)
download | inline diff:diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgmlindex 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.cindex 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.cindex 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.datindex 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.outindex 8c255b9e4d..cca47af7fb 100644--- a/src/test/regress/expected/int2.out+++ b/src/test/regress/expected/int2.out@@ -306,3 +306,23 @@ 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, (-32768)::int2);+ gcd +--------+ -32768+(1 row)+diff --git a/src/test/regress/expected/int4.out b/src/test/regress/expected/int4.outindex bda7a8daef..3f0f37ffc7 100644--- a/src/test/regress/expected/int4.out+++ b/src/test/regress/expected/int4.out@@ -403,3 +403,23 @@ 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, (-2147483648)::int4);+ gcd +-------------+ -2147483648+(1 row)+diff --git a/src/test/regress/expected/int8.out b/src/test/regress/expected/int8.outindex 8447a28c3d..d6d1a76b29 100644--- a/src/test/regress/expected/int8.out+++ b/src/test/regress/expected/int8.out@@ -886,3 +886,23 @@ 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, (-9223372036854775808)::int8);+ gcd +----------------------+ -9223372036854775808+(1 row)+diff --git a/src/test/regress/sql/int2.sql b/src/test/regress/sql/int2.sqlindex 7dbafb6dac..656b200e5e 100644--- a/src/test/regress/sql/int2.sql+++ b/src/test/regress/sql/int2.sql@@ -112,3 +112,10 @@ 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, (-32768)::int2);diff --git a/src/test/regress/sql/int4.sql b/src/test/regress/sql/int4.sqlindex f014cb2d32..1faea33945 100644--- a/src/test/regress/sql/int4.sql+++ b/src/test/regress/sql/int4.sql@@ -155,3 +155,10 @@ 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, (-2147483648)::int4);diff --git a/src/test/regress/sql/int8.sql b/src/test/regress/sql/int8.sqlindex e890452236..af9501c415 100644--- a/src/test/regress/sql/int8.sql+++ b/src/test/regress/sql/int8.sql@@ -225,3 +225,10 @@ 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, (-9223372036854775808)::int8);
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, coelho@cri.ensmp.fr, pgsql-hackers@lists.postgresql.org
Subject: Re: Greatest Common Divisor
In-Reply-To: <dbf86808-91fa-3262-f939-2ef3d38ec242@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