Re: Greatest Common Divisor

On 28/12/2019 19:15, Fabien COELHO wrote:
>
>> 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.


I decided against it for that reason.


> Should there be a NUMERIC version as well? I'd say maybe yes.


I thought about that, too, but also decided against it for this patch.


> 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.


Well, gcd(N, 0) is N, and gcd(0, 0) is 0, so I don't see an issue here?


> I'd test with INT_MIN and INT_MAX.


Okay, I'll add tests for those, instead of the pretty much random values
I have now.


> Given that there are no overflows risk with the Euclidian descent, would
> it make sense that the int2 version call the int4 implementation?


Meh.


>
> C modulo operator (%) is a pain because it is not positive remainder
> (2 % -3 == -1 vs 2 % 3 == 2, AFAICR). 


This does not seem to be the case...


> 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.


Why isn't it the right thing to do?


> Which raises an issue with INT_MIN by the way, which has no positive:-(


That's an argument against abs-ing the input values.  It's only an issue
with gcd(INT_MIN, INT_MIN) which currently returns INT_MIN.  Any other
value with INT_MIN will be 1 or something lower than INT_MAX.


> 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:-)


The args will exchange themselves.


Thanks for the review!  Attached is a new patch that changes the
regression tests based on your comments (and another comment that I got
on irc to test gcd(b, a)).