From: Fabien COELHO <coelho@cri.ensmp.fr>
To: Vik Fearing <vik.fearing@2ndquadrant.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
Date: Sat, 28 Dec 2019 19:15:03 +0100 (CET)
Message-ID: <alpine.DEB.2.21.1912281848540.24861@pseudo> (raw)
In-Reply-To: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
References: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
Bonsoir Vik,
> I recently came across the need for a gcd function (actually I needed
> lcm) and was surprised that we didn't have one.
Why not.
> 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.
Should there be a NUMERIC version as well? I'd say maybe yes.
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.
I'd test with INT_MIN and INT_MAX.
Given that there are no overflows risk with the Euclidian descent, would
it make sense that the int2 version call the int4 implementation?
C modulo operator (%) is a pain because it is not positive remainder (2 %
-3 == -1 vs 2 % 3 == 2, AFAICR). 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.
Which raises an issue with INT_MIN by the way, which has no positive:-(
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:-)
See for instance (the int min value is probably not well handled):
https://svn.cri.ensmp.fr/svn/linear/trunk/src/arithmetique/pgcd.c
Basically, welcome to arithmetic:-)
--
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, pgsql-hackers@lists.postgresql.org
Subject: Re: Greatest Common Divisor
In-Reply-To: <alpine.DEB.2.21.1912281848540.24861@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