Date: Sat, 28 Dec 2019 19:15:03 +0100 (CET)
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
In-Reply-To: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
Message-ID: <alpine.DEB.2.21.1912281848540.24861@pseudo>
References: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
User-Agent: Alpine 2.21 (DEB 202 2017-01-01)
MIME-Version: 1.0
Content-Type: multipart/mixed;
 boundary="2056645051-1183991715-1577556906=:24861"
Precedence: bulk

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--2056645051-1183991715-1577556906=:24861
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8BIT


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.
--2056645051-1183991715-1577556906=:24861--