Date: Sun, 29 Dec 2019 08:30:26 +0100 (CET)
From: Fabien COELHO <coelho@cri.ensmp.fr>
To: Vik Fearing <vik.fearing@2ndquadrant.com>
cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
In-Reply-To: <dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com>
Message-ID: <alpine.DEB.2.21.1912290815520.889@pseudo>
References: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
 <alpine.DEB.2.21.1912281848540.24861@pseudo>
 <dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com>
User-Agent: Alpine 2.21 (DEB 202 2017-01-01)
MIME-Version: 1.0
Content-Type: multipart/mixed;
 boundary="2056645051-1661852082-1577604628=:889"
Precedence: bulk

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--2056645051-1661852082-1577604628=:889
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8BIT


Bonjour Vik,

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

Hmmm. ISTM that int functions are available for numeric?

>> 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 think that there should be a comment.

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

Indeed, I tested quickly with python, but it has yet another behavior as 
shown above, what a laugh!

So with C: 2 % -3 == 2, -2 % 3 == -2

Note that AFAICS there is no integer i so that 3 * i - (-2) == -2.

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

Because I do not trust C modulo as I had a lot of problems with it? :-)

If it works, but it should deserve a clear comment explaining why.

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

That should be an error instead, because -INT_MIN cannot be represented?

> Any other value with INT_MIN will be 1 or something lower than INT_MAX.

Looks ok.

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

Yep, but after a possibly expensive software-emulated modulo operation?

-- 
Fabien.
--2056645051-1661852082-1577604628=:889--