Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1inRms-00047Q-Aw for pgsql-hackers@arkaria.postgresql.org; Fri, 03 Jan 2020 18:35:06 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1inRmr-0002Qs-1t for pgsql-hackers@arkaria.postgresql.org; Fri, 03 Jan 2020 18:35:05 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1inRmq-0002Qj-Gc for pgsql-hackers@lists.postgresql.org; Fri, 03 Jan 2020 18:35:04 +0000 Received: from mail-wr1-x434.google.com ([2a00:1450:4864:20::434]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1inRmm-0007zZ-Vo for pgsql-hackers@lists.postgresql.org; Fri, 03 Jan 2020 18:35:03 +0000 Received: by mail-wr1-x434.google.com with SMTP id j42so43243350wrj.12 for ; Fri, 03 Jan 2020 10:35:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=2ndquadrant-com.20150623.gappssmtp.com; s=20150623; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-language; bh=kYLNOBGY+sq2J6FxdISLa13lumSG/gB3yDC5kNOBaS4=; b=Iu47RWQKEpsY1zUYEotUt/qA18JBDPtY7wosUBtbhiRJoNZneWJ/GmOQSqG3rO6cKd hcJ0w0ag++sx/Lr2lEkBEfy/xEFMP7cIZp/eoY4EqS4HJ3BMlN5ce6mOGtkjBO0Nd3lA sQcusdgbwsa4ucgpQ5aQSMz8QBI6nevPFyc4JqiNSaNGAfRdyg+PUG3cmuslZMotap2w kDHe8IDuBeP5NXlv584ALM/RfCq99EdPYbL+t38cJBEGPvzKvaGQrWrRy38dTbHBpnAQ +igUFhphC3k9KhQvvKPwediwa9mg1Ss+QsbvWhl8PMtc4VRLwEUjFeAqJVwAlUWU/1Vl jh9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=kYLNOBGY+sq2J6FxdISLa13lumSG/gB3yDC5kNOBaS4=; b=H7EyyWx4ulib2x3dcCHyvINhmx89fVgIflyY+8xq4KOa+Fejn+VwfrZvEspym5PYIi Re5SA/2vKjX1umLxgRrG187TTQjHz7/oBvUVLTo9kdVrVfB5lLXYckwYGVJfBiS5i8Ok 5AZSgyrpHDwy3Duv8Ba8OQiYNkn1XhfXxggKnjemW17MkidTMpoJKHOz9HQZ3GxVqx8e 1FqomhzuAaaMJGPRrmlHVqjdKmbo+YD3FJ+bSGXpA2s8k2gdNcwUs5+2JQn2yOvsBCTm gZqz65yCufmAeuh0aAIGavsSFui5MLrIFrclmWs8/yUt2QjN1uRWiBIjD+ZQq3PVNp2P l1lA== X-Gm-Message-State: APjAAAVw3C+58NrhkxP19HyhqADHCk0ngXTmT9VYYkFeSp32wBxFWJh9 h3CM+lGV+6FDCYMvo5a97M8ANLzsoVB4H3Pkf7L81W42dX4iZSDpEHPJ1aHFiunugD6lHnKkTl9 hW7qdwhKYNaN9YvBqgnZ5WKCa2mNJYXMKRNeo72rtvjjTC+vKLXX9AncFHO0KkAyWX3XpGBsdin xetBgYdCCSw4QhtJcMgg== X-Google-Smtp-Source: APXvYqyu2CVKcdyJsv3yUolvaMiiOVkyzKIUSnDsa+bSwofd6gqS1yc3hstqw3juuPa7xO3s4qAlAg== X-Received: by 2002:adf:ea8a:: with SMTP id s10mr87314150wrm.278.1578076499058; Fri, 03 Jan 2020 10:34:59 -0800 (PST) Received: from [10.8.8.7] ([185.94.189.189]) by smtp.gmail.com with ESMTPSA id q68sm13889665wme.14.2020.01.03.10.34.56 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 03 Jan 2020 10:34:58 -0800 (PST) Subject: Re: Greatest Common Divisor To: Tom Lane , Stephen Frost Cc: Dean Rasheed , Fabien COELHO , Chapman Flack , PostgreSQL Hackers References: <5E08D947.9000902@anastigmatix.net> <20200102145712.GN3195@tamriel.snowman.net> <16242.1577977961@sss.pgh.pa.us> From: Vik Fearing Message-ID: <6855727c-3836-21cc-18f9-e79227b99079@2ndquadrant.com> Date: Fri, 3 Jan 2020 19:34:55 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.2 MIME-Version: 1.0 In-Reply-To: <16242.1577977961@sss.pgh.pa.us> Content-Type: multipart/mixed; boundary="------------ED978F31653FB4B89D9A756F" Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk This is a multi-part message in MIME format. --------------ED978F31653FB4B89D9A756F Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit On 02/01/2020 16:12, Tom Lane wrote: > Stephen Frost writes: >> * Dean Rasheed (dean.a.rasheed@gmail.com) 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 --------------ED978F31653FB4B89D9A756F Content-Type: text/x-patch; charset=UTF-8; name="gcd.0004.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="gcd.0004.patch" 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 @@ -43 + + + + gcd + + gcd(a, b) + + (same as argument types) + greatest common divisor + gcd(1071, 462) + 21 + + + + + + lcm + + lcm(a, b) + + (same as argument types) + least common multiple + lcm(1071, 462) + 23562 + + 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 --------------ED978F31653FB4B89D9A756F--