Re: Greatest Common Divisor
От | Fabien COELHO |
---|---|
Тема | Re: Greatest Common Divisor |
Дата | |
Msg-id | alpine.DEB.2.21.1912281848540.24861@pseudo обсуждение исходный текст |
Ответ на | Greatest Common Divisor (Vik Fearing <vik.fearing@2ndquadrant.com>) |
Ответы |
Re: Greatest Common Divisor
Re: Greatest Common Divisor |
Список | pgsql-hackers |
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.
В списке pgsql-hackers по дате отправления: