Re: Greatest Common Divisor

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.