From: Fabien COELHO <coelho@cri.ensmp.fr>
To: Vik Fearing <vik.fearing@2ndquadrant.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Stephen Frost <sfrost@snowman.net>
Cc: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Chapman Flack <chap@anastigmatix.net>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
Date: Sat, 4 Jan 2020 22:21:15 +0100 (CET)
Message-ID: <alpine.DEB.2.21.2001042051170.6753@pseudo> (raw)
In-Reply-To: <13b5bbd5-6784-528f-9fd7-9fa43250be51@2ndquadrant.com>
References: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
<alpine.DEB.2.21.1912281848540.24861@pseudo>
<dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com>
<alpine.DEB.2.21.1912290815520.889@pseudo>
<5E08D947.9000902@anastigmatix.net>
<alpine.DEB.2.21.1912291755510.14206@pseudo>
<CAEZATCX9YgkWupVFcJ5ixkEJMyf2X5ZecN8K5r12oOB8mDHzWQ@mail.gmail.com>
<20200102145712.GN3195@tamriel.snowman.net>
<16242.1577977961@sss.pgh.pa.us>
<6855727c-3836-21cc-18f9-e79227b99079@2ndquadrant.com>
<alpine.DEB.2.21.2001032010470.12030@pseudo>
<32b8af34-8f87-c30f-5555-2325bd140a59@2ndquadrant.com>
<alpine.DEB.2.21.2001041003090.31333@pseudo>
<13b5bbd5-6784-528f-9fd7-9fa43250be51@2ndquadrant.com>
Hello Vik,
>> Add unlikely() where appropriate.
>
> Any particular place in mind where I didn't already put it?
In GCD implementations, for instance:
if (arg1 == PG_INT32_MIN)
if (arg2 == 0 || arg2 == PG_INT32_MIN)
And possibly a "likely" on the while.
In LCM implementations, for instance:
if (arg1 == 0 || arg2 == 0)
if (arg1 == arg2)
The later is partially redundant with preceeding case BTW, which could be
managed inside this one, reducing the number of tests? Something like:
if (arg1 == arg2)
if (arg1 == MIN_INT)
error
else
return abs(arg1)
I'm not sure why you want to deal with a1 == a2 case separately, could it
not just work with the main code?
If you want to deal with it separately, then why not doing arg1 == -arg2
as well?
> Please stop suggesting it.
Fine, fine!
Tom also suggested to align implementations as much as possible, and I do
agree with him.
Also, I'd suggest to add a comment to explain that the precise C99 modulo
semantics is required to make the algorithm work, and that it may not work
with C89 semantics for instance.
>> Note: in the numeric code you abs the value, ISTM consistent to do it
>> as well in the other implementations.
>
> As noted in the comments, numeric does not have the INT_MIN problem.
Sure, but there are special cases at the beginning all the same: NAN,
INTEGRAL…
>> Would it make sense that NAN is returned on NUMERIC when the
>> computation cannot be performed, eg on non integer values?
>
> I don't think so, no.
Ok. Why? I do not have an opinion, but ISTM that there is a choice and it
should be explained. Could be consistency with other cases, whatever.
>> Why the positive constraint on LCM(NUMERIC, NUMERIC)? Why not absoluting?
>
> I didn't see a definition for negative inputs, but now I see one so I've
> lifted the restriction.
Good.
About tests: again, I'd check the LCM overflow on smaller values.
I'm not convinced by the handling of fractional numerics in gcd, eg:
+SELECT gcd(330.3::numeric, 462::numeric);
+ gcd
+-----
+ 0.3
+(1 row)
ISTM that the average user, including myself, would expect an integer
result from gcd.
If this is kept, the documentation should be clear about what it does and
what it means, because the least to say is that it is surprising.
Somehow I could have expected the arguments to be casted to int, so that
it would lead to 66.
Python does a type error, which I find even better. I'd vote for erroring.
If this fractional gcd makes some sense and is desirable, then ISTM that
lcm(a,b) = a / gcd(a, b) * b should make as much sense and should be
allowed as well, for consistency.
--
Fabien.
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: coelho@cri.ensmp.fr, vik.fearing@2ndquadrant.com, tgl@sss.pgh.pa.us, sfrost@snowman.net, dean.a.rasheed@gmail.com, chap@anastigmatix.net, pgsql-hackers@lists.postgresql.org
Subject: Re: Greatest Common Divisor
In-Reply-To: <alpine.DEB.2.21.2001042051170.6753@pseudo>
* 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