Add functions gcd() and lcm() for integer and numeric types.

These compute the greatest common divisor and least common multiple of
a pair of numbers using the Euclidean algorithm.

Vik Fearing, reviewed by Fabien Coelho.

Discussion: https://postgr.es/m/adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com

6 files changed, 211 insertions, 0 deletions

diff --git a/src/test/regress/expected/int4.out b/src/test/regress/expected/int4.out
index bda7a8daefc..c384af18ee8 100644
--- a/src/test/regress/expected/int4.out
+++ b/src/test/regress/expected/int4.out
@@ -403,3 +403,49 @@ FROM (VALUES (-2.5::numeric),
   2.5 |          3
 (7 rows)
 
+-- test gcd()
+SELECT a, b, gcd(a, b), gcd(a, -b), gcd(b, a), gcd(-b, a)
+FROM (VALUES (0::int4, 0::int4),
+             (0::int4, 6410818::int4),
+             (61866666::int4, 6410818::int4),
+             (-61866666::int4, 6410818::int4),
+             ((-2147483648)::int4, 1::int4),
+             ((-2147483648)::int4, 2147483647::int4),
+             ((-2147483648)::int4, 1073741824::int4)) AS v(a, b);
+      a      |     b      |    gcd     |    gcd     |    gcd     |    gcd     
+-------------+------------+------------+------------+------------+------------
+           0 |          0 |          0 |          0 |          0 |          0
+           0 |    6410818 |    6410818 |    6410818 |    6410818 |    6410818
+    61866666 |    6410818 |       1466 |       1466 |       1466 |       1466
+   -61866666 |    6410818 |       1466 |       1466 |       1466 |       1466
+ -2147483648 |          1 |          1 |          1 |          1 |          1
+ -2147483648 | 2147483647 |          1 |          1 |          1 |          1
+ -2147483648 | 1073741824 | 1073741824 | 1073741824 | 1073741824 | 1073741824
+(7 rows)
+
+SELECT gcd((-2147483648)::int4, 0::int4); -- overflow
+ERROR:  integer out of range
+SELECT gcd((-2147483648)::int4, (-2147483648)::int4); -- overflow
+ERROR:  integer out of range
+-- test lcm()
+SELECT a, b, lcm(a, b), lcm(a, -b), lcm(b, a), lcm(-b, a)
+FROM (VALUES (0::int4, 0::int4),
+             (0::int4, 42::int4),
+             (42::int4, 42::int4),
+             (330::int4, 462::int4),
+             (-330::int4, 462::int4),
+             ((-2147483648)::int4, 0::int4)) AS v(a, b);
+      a      |  b  | lcm  | lcm  | lcm  | lcm  
+-------------+-----+------+------+------+------
+           0 |   0 |    0 |    0 |    0 |    0
+           0 |  42 |    0 |    0 |    0 |    0
+          42 |  42 |   42 |   42 |   42 |   42
+         330 | 462 | 2310 | 2310 | 2310 | 2310
+        -330 | 462 | 2310 | 2310 | 2310 | 2310
+ -2147483648 |   0 |    0 |    0 |    0 |    0
+(6 rows)
+
+SELECT lcm((-2147483648)::int4, 1::int4); -- overflow
+ERROR:  integer out of range
+SELECT lcm(2147483647::int4, 2147483646::int4); -- overflow
+ERROR:  integer out of range
diff --git a/src/test/regress/expected/int8.out b/src/test/regress/expected/int8.out
index 8447a28c3d3..813e3a82866 100644
--- a/src/test/regress/expected/int8.out
+++ b/src/test/regress/expected/int8.out
@@ -886,3 +886,49 @@ FROM (VALUES (-2.5::numeric),
   2.5 |          3
 (7 rows)
 
+-- test gcd()
+SELECT a, b, gcd(a, b), gcd(a, -b), gcd(b, a), gcd(-b, a)
+FROM (VALUES (0::int8, 0::int8),
+             (0::int8, 29893644334::int8),
+             (288484263558::int8, 29893644334::int8),
+             (-288484263558::int8, 29893644334::int8),
+             ((-9223372036854775808)::int8, 1::int8),
+             ((-9223372036854775808)::int8, 9223372036854775807::int8),
+             ((-9223372036854775808)::int8, 4611686018427387904::int8)) AS v(a, b);
+          a           |          b          |         gcd         |         gcd         |         gcd         |         gcd         
+----------------------+---------------------+---------------------+---------------------+---------------------+---------------------
+                    0 |                   0 |                   0 |                   0 |                   0 |                   0
+                    0 |         29893644334 |         29893644334 |         29893644334 |         29893644334 |         29893644334
+         288484263558 |         29893644334 |             6835958 |             6835958 |             6835958 |             6835958
+        -288484263558 |         29893644334 |             6835958 |             6835958 |             6835958 |             6835958
+ -9223372036854775808 |                   1 |                   1 |                   1 |                   1 |                   1
+ -9223372036854775808 | 9223372036854775807 |                   1 |                   1 |                   1 |                   1
+ -9223372036854775808 | 4611686018427387904 | 4611686018427387904 | 4611686018427387904 | 4611686018427387904 | 4611686018427387904
+(7 rows)
+
+SELECT gcd((-9223372036854775808)::int8, 0::int8); -- overflow
+ERROR:  bigint out of range
+SELECT gcd((-9223372036854775808)::int8, (-9223372036854775808)::int8); -- overflow
+ERROR:  bigint out of range
+-- test lcm()
+SELECT a, b, lcm(a, b), lcm(a, -b), lcm(b, a), lcm(-b, a)
+FROM (VALUES (0::int8, 0::int8),
+             (0::int8, 29893644334::int8),
+             (29893644334::int8, 29893644334::int8),
+             (288484263558::int8, 29893644334::int8),
+             (-288484263558::int8, 29893644334::int8),
+             ((-9223372036854775808)::int8, 0::int8)) AS v(a, b);
+          a           |      b      |       lcm        |       lcm        |       lcm        |       lcm        
+----------------------+-------------+------------------+------------------+------------------+------------------
+                    0 |           0 |                0 |                0 |                0 |                0
+                    0 | 29893644334 |                0 |                0 |                0 |                0
+          29893644334 | 29893644334 |      29893644334 |      29893644334 |      29893644334 |      29893644334
+         288484263558 | 29893644334 | 1261541684539134 | 1261541684539134 | 1261541684539134 | 1261541684539134
+        -288484263558 | 29893644334 | 1261541684539134 | 1261541684539134 | 1261541684539134 | 1261541684539134
+ -9223372036854775808 |           0 |                0 |                0 |                0 |                0
+(6 rows)
+
+SELECT lcm((-9223372036854775808)::int8, 1::int8); -- overflow
+ERROR:  bigint out of range
+SELECT lcm(9223372036854775807::int8, 9223372036854775806::int8); -- overflow
+ERROR:  bigint out of range
diff --git a/src/test/regress/expected/numeric.out b/src/test/regress/expected/numeric.out
index 8acfa394245..23a4c6dcc3f 100644
--- a/src/test/regress/expected/numeric.out
+++ b/src/test/regress/expected/numeric.out
@@ -2220,3 +2220,47 @@ SELECT SUM((-9999)::numeric) FROM generate_series(1, 100000);
  -999900000
 (1 row)
 
+--
+-- Tests for GCD()
+--
+SELECT a, b, gcd(a, b), gcd(a, -b), gcd(-b, a), gcd(-b, -a)
+FROM (VALUES (0::numeric, 0::numeric),
+             (0::numeric, numeric 'NaN'),
+             (0::numeric, 46375::numeric),
+             (433125::numeric, 46375::numeric),
+             (43312.5::numeric, 4637.5::numeric),
+             (4331.250::numeric, 463.75000::numeric)) AS v(a, b);
+    a     |     b     |   gcd   |   gcd   |   gcd   |   gcd   
+----------+-----------+---------+---------+---------+---------
+        0 |         0 |       0 |       0 |       0 |       0
+        0 |       NaN |     NaN |     NaN |     NaN |     NaN
+        0 |     46375 |   46375 |   46375 |   46375 |   46375
+   433125 |     46375 |     875 |     875 |     875 |     875
+  43312.5 |    4637.5 |    87.5 |    87.5 |    87.5 |    87.5
+ 4331.250 | 463.75000 | 8.75000 | 8.75000 | 8.75000 | 8.75000
+(6 rows)
+
+--
+-- Tests for LCM()
+--
+SELECT a,b, lcm(a, b), lcm(a, -b), lcm(-b, a), lcm(-b, -a)
+FROM (VALUES (0::numeric, 0::numeric),
+             (0::numeric, numeric 'NaN'),
+             (0::numeric, 13272::numeric),
+             (13272::numeric, 13272::numeric),
+             (423282::numeric, 13272::numeric),
+             (42328.2::numeric, 1327.2::numeric),
+             (4232.820::numeric, 132.72000::numeric)) AS v(a, b);
+    a     |     b     |     lcm      |     lcm      |     lcm      |     lcm      
+----------+-----------+--------------+--------------+--------------+--------------
+        0 |         0 |            0 |            0 |            0 |            0
+        0 |       NaN |          NaN |          NaN |          NaN |          NaN
+        0 |     13272 |            0 |            0 |            0 |            0
+    13272 |     13272 |        13272 |        13272 |        13272 |        13272
+   423282 |     13272 |     11851896 |     11851896 |     11851896 |     11851896
+  42328.2 |    1327.2 |    1185189.6 |    1185189.6 |    1185189.6 |    1185189.6
+ 4232.820 | 132.72000 | 118518.96000 | 118518.96000 | 118518.96000 | 118518.96000
+(7 rows)
+
+SELECT lcm(9999 * (10::numeric)^131068 + (10::numeric^131068 - 1), 2); -- overflow
+ERROR:  value overflows numeric format
diff --git a/src/test/regress/sql/int4.sql b/src/test/regress/sql/int4.sql
index f014cb2d325..a9e90a96c4c 100644
--- a/src/test/regress/sql/int4.sql
+++ b/src/test/regress/sql/int4.sql
@@ -155,3 +155,28 @@ FROM (VALUES (-2.5::numeric),
              (0.5::numeric),
              (1.5::numeric),
              (2.5::numeric)) t(x);
+
+-- test gcd()
+SELECT a, b, gcd(a, b), gcd(a, -b), gcd(b, a), gcd(-b, a)
+FROM (VALUES (0::int4, 0::int4),
+             (0::int4, 6410818::int4),
+             (61866666::int4, 6410818::int4),
+             (-61866666::int4, 6410818::int4),
+             ((-2147483648)::int4, 1::int4),
+             ((-2147483648)::int4, 2147483647::int4),
+             ((-2147483648)::int4, 1073741824::int4)) AS v(a, b);
+
+SELECT gcd((-2147483648)::int4, 0::int4); -- overflow
+SELECT gcd((-2147483648)::int4, (-2147483648)::int4); -- overflow
+
+-- test lcm()
+SELECT a, b, lcm(a, b), lcm(a, -b), lcm(b, a), lcm(-b, a)
+FROM (VALUES (0::int4, 0::int4),
+             (0::int4, 42::int4),
+             (42::int4, 42::int4),
+             (330::int4, 462::int4),
+             (-330::int4, 462::int4),
+             ((-2147483648)::int4, 0::int4)) AS v(a, b);
+
+SELECT lcm((-2147483648)::int4, 1::int4); -- overflow
+SELECT lcm(2147483647::int4, 2147483646::int4); -- overflow
diff --git a/src/test/regress/sql/int8.sql b/src/test/regress/sql/int8.sql
index e890452236f..dba3ade687a 100644
--- a/src/test/regress/sql/int8.sql
+++ b/src/test/regress/sql/int8.sql
@@ -225,3 +225,28 @@ FROM (VALUES (-2.5::numeric),
              (0.5::numeric),
              (1.5::numeric),
              (2.5::numeric)) t(x);
+
+-- test gcd()
+SELECT a, b, gcd(a, b), gcd(a, -b), gcd(b, a), gcd(-b, a)
+FROM (VALUES (0::int8, 0::int8),
+             (0::int8, 29893644334::int8),
+             (288484263558::int8, 29893644334::int8),
+             (-288484263558::int8, 29893644334::int8),
+             ((-9223372036854775808)::int8, 1::int8),
+             ((-9223372036854775808)::int8, 9223372036854775807::int8),
+             ((-9223372036854775808)::int8, 4611686018427387904::int8)) AS v(a, b);
+
+SELECT gcd((-9223372036854775808)::int8, 0::int8); -- overflow
+SELECT gcd((-9223372036854775808)::int8, (-9223372036854775808)::int8); -- overflow
+
+-- test lcm()
+SELECT a, b, lcm(a, b), lcm(a, -b), lcm(b, a), lcm(-b, a)
+FROM (VALUES (0::int8, 0::int8),
+             (0::int8, 29893644334::int8),
+             (29893644334::int8, 29893644334::int8),
+             (288484263558::int8, 29893644334::int8),
+             (-288484263558::int8, 29893644334::int8),
+             ((-9223372036854775808)::int8, 0::int8)) AS v(a, b);
+
+SELECT lcm((-9223372036854775808)::int8, 1::int8); -- overflow
+SELECT lcm(9223372036854775807::int8, 9223372036854775806::int8); -- overflow
diff --git a/src/test/regress/sql/numeric.sql b/src/test/regress/sql/numeric.sql
index e611cc4d8dc..c5c8d76727d 100644
--- a/src/test/regress/sql/numeric.sql
+++ b/src/test/regress/sql/numeric.sql
@@ -1073,3 +1073,28 @@ select trim_scale(1e100);
 -- 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 a, b, gcd(a, b), gcd(a, -b), gcd(-b, a), gcd(-b, -a)
+FROM (VALUES (0::numeric, 0::numeric),
+             (0::numeric, numeric 'NaN'),
+             (0::numeric, 46375::numeric),
+             (433125::numeric, 46375::numeric),
+             (43312.5::numeric, 4637.5::numeric),
+             (4331.250::numeric, 463.75000::numeric)) AS v(a, b);
+
+--
+-- Tests for LCM()
+--
+SELECT a,b, lcm(a, b), lcm(a, -b), lcm(-b, a), lcm(-b, -a)
+FROM (VALUES (0::numeric, 0::numeric),
+             (0::numeric, numeric 'NaN'),
+             (0::numeric, 13272::numeric),
+             (13272::numeric, 13272::numeric),
+             (423282::numeric, 13272::numeric),
+             (42328.2::numeric, 1327.2::numeric),
+             (4232.820::numeric, 132.72000::numeric)) AS v(a, b);
+
+SELECT lcm(9999 * (10::numeric)^131068 + (10::numeric^131068 - 1), 2); -- overflow