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.
