From: | Vik Fearing <vik(dot)fearing(at)2ndquadrant(dot)com> |
---|---|
To: | Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr> |
Cc: | PostgreSQL Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org> |
Subject: | Re: Greatest Common Divisor |
Date: | 2019-12-28 22:03:59 |
Message-ID: | dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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)).
Attachment | Content-Type | Size |
---|---|---|
gcd.0002.patch | text/x-patch | 6.9 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2019-12-28 22:33:18 | Re: use CLZ instruction in AllocSetFreeIndex() |
Previous Message | Robert Haas | 2019-12-28 21:55:55 | Re: Disallow cancellation of waiting for synchronous replication |