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)).
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..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.out index 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.out index 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.sql index 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.sql index 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.sql index 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);