Date: Sun, 29 Dec 2019 18:13:32 +0100 (CET)
From: Fabien COELHO <coelho@cri.ensmp.fr>
To: Chapman Flack <chap@anastigmatix.net>
cc: Vik Fearing <vik.fearing@2ndquadrant.com>,
    PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
In-Reply-To: <5E08D947.9000902@anastigmatix.net>
Message-ID: <alpine.DEB.2.21.1912291755510.14206@pseudo>
References: <adbd3e0b-e3f1-5bbc-21db-03caf1cef0f7@2ndquadrant.com>
 <alpine.DEB.2.21.1912281848540.24861@pseudo>
 <dbf86808-91fa-3262-f939-2ef3d38ec242@2ndquadrant.com>
 <alpine.DEB.2.21.1912290815520.889@pseudo>
 <5E08D947.9000902@anastigmatix.net>
User-Agent: Alpine 2.21 (DEB 202 2017-01-01)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII; format=flowed
Precedence: bulk


Hello,

>> Because I do not trust C modulo as I had a lot of problems with it?:-)
>
> If I recall correctly (and I'm traveling and away from those notes),
> the exact semantics of C's % with negative operands was left
> implementation-defined until, was it, C99 ?

Indeed, my woes with C % started before that date:-)

By Googling the C99 spec, I found: "When integers are divided, the result 
of the / operator is the algebraic quotient with any fractional part 
discarded (aka truncation toward zero). If the quotient a/b is 
representable, the expression (a/b)*b + a%b shall equal a."

Let a = 2 and b = -3, then a/b == 0 (-0.666 truncated toward zero), then

    (a/b)*b + a%b == a

=> 0 * -3 + (2 % -3) == 2

=> 2 % -3 == 2

Then with a = -2, b = 3, then a/b == 0 (same as above), and the same 
reasoning leads to

    -2 % 3 == -2

Which is indeed what was produced with C, but not with Python.

The good news is that the absolute value of the modulo is the module in 
the usual sense, which is what is needed for the Euclidian descent and 
allows fixing the sign afterwards, as Vik was doing.

> So it might be ok to rely on the specified C99 behavior (whichever
> behavior that is, he wrote, notelessly) for PG 12 and later, where
> C99 is expected.

Yep, probably with a comment.

-- 
Fabien.