On 25/01/2020 15:18, Dean Rasheed wrote:
>
> Committed with some adjustments, mostly cosmetic but a couple more
> substantive:
Thanks!
> The code to guard against a floating point exception with inputs of
> (INT_MIN, -1) wasn't quite right because it actually just moved the
> problem so that it
On Mon, 20 Jan 2020 at 08:04, Vik Fearing wrote:
>
> On 20/01/2020 08:44, Dean Rasheed wrote:
> >>
> > I see this has been marked RFC. I'll take it,
>
Committed with some adjustments, mostly cosmetic but a couple more substantive:
The code to guard against a floating point exception with inputs
On Mon, 20 Jan 2020 at 19:04, Alvaro Herrera wrote:
>
> On 2020-Jan-20, Dean Rasheed wrote:
>
> > +
> > + greatest common divisor — the largest positive number that
> > +divides both inputs with no remainder; returns
> > 0 if
On Mon, 20 Jan 2020 at 18:52, Vik Fearing wrote:
>
> On 20/01/2020 11:28, Dean Rasheed wrote:
> >
> > +
> > +least common multiple — the smallest strictly positive number
> > +that is an integer multiple of both inputs; returns
> > 0
> > +if either input is zero
> >
On 2020-Jan-20, Dean Rasheed wrote:
> +
> + greatest common divisor — the largest positive number that
> +divides both inputs with no remainder; returns 0
> if
> +both inputs are zero
> +
Warning, severe TOC/bikeshedding ahead.
I don&#x
ose the following:
>
> +
> + greatest common divisor — the largest positive number that
> +divides both inputs with no remainder; returns 0
> if
> +both inputs are zero
> +
>
> and:
>
> +
> +least common multiple — the sm
Looking at the docs, I think it's worth going a little further than
just saying what the acronyms stand for -- especially since the
behaviour for zero inputs is an implementation choice (albeit the most
common one). I propose the following:
+
+ greatest common divisor — the la
On 20/01/2020 08:44, Dean Rasheed wrote:
> On Tue, 7 Jan 2020 at 12:31, Tom Lane wrote:
>> Dean Rasheed writes:
>>> Do we actually need the smallint versions of these functions?
>> Doubt it. It'd be fairly hard even to call those, since e.g. "42"
>> is an int not a smallint.
>>
> I see this has
On Tue, 7 Jan 2020 at 12:31, Tom Lane wrote:
>
> Dean Rasheed writes:
> > Do we actually need the smallint versions of these functions?
>
> Doubt it. It'd be fairly hard even to call those, since e.g. "42"
> is an int not a smallint.
>
I see this has been marked RFC. I'll take it, and barring o
Dean Rasheed writes:
> Do we actually need the smallint versions of these functions?
Doubt it. It'd be fairly hard even to call those, since e.g. "42"
is an int not a smallint.
regards, tom lane
Do we actually need the smallint versions of these functions?
I would have thought that automatic casting would take care of any
cases that need smallints, and I can't believe that there's any
performance benefit to be had that's worth maintaining the extra code.
Regards,
Dean
Hello Merlin,
For low-level arithmetic code like this one, with tests and loops
containing very few hardware instructions, I think that helping compiler
optimizations is a good idea.
Do you have any performance data to back that up?
Yep.
A generic data is the woes about speculative executi
On Mon, Jan 6, 2020 at 6:52 AM Fabien COELHO wrote:
>
>
> Hello Robert,
>
> >> if (arg1 == PG_INT32_MIN)
> >> if (arg2 == 0 || arg2 == PG_INT32_MIN)
> >>
> >> And possibly a "likely" on the while.
> >
> > I don't think decoration the code with likely() and unlikely() all
> > over the place is
Hello Robert,
if (arg1 == PG_INT32_MIN)
if (arg2 == 0 || arg2 == PG_INT32_MIN)
And possibly a "likely" on the while.
I don't think decoration the code with likely() and unlikely() all
over the place is a very good idea.
Odds are good that we'll end up with a bunch that are actually
no
On Sat, Jan 4, 2020 at 4:21 PM Fabien COELHO wrote:
> In GCD implementations, for instance:
>
> if (arg1 == PG_INT32_MIN)
> if (arg2 == 0 || arg2 == PG_INT32_MIN)
>
> And possibly a "likely" on the while.
I don't think decoration the code with likely() and unlikely() all
over the place is a v
lcm(a, b)
+
+ (same as argument types)
+ least common multiple
+ lcm(1071, 462)
+ 23562
+
+
diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c
index 583ce71e66..53673a8dea 100644
--- a/src/backend/utils/adt/i
Hello Vik,
Add unlikely() where appropriate.
Any particular place in mind where I didn't already put it?
In GCD implementations, for instance:
if (arg1 == PG_INT32_MIN)
if (arg2 == 0 || arg2 == PG_INT32_MIN)
And possibly a "likely" on the while.
In LCM implementations, for instance:
On Sat, 4 Jan 2020 at 17:55, Vik Fearing wrote:
> On 04/01/2020 10:37, Dean Rasheed wrote:
> >
> > BTW, there is actually no need to restrict the inputs to integral
> > values because GCD is something that has a perfectly natural extension
> > to floating point inputs (see for example [1]). Moreov
INTERRUPTS in the loop would be well-advised,
> if there's not one already inside the called functions.
Good idea. Added.
--
Vik Fearing
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 57a1539506..e2b7d6d240 100644
--- a/doc/src/sgml/func.sgml
+++ b/do
Dean Rasheed writes:
> OTOH, for numeric inputs, this could easily end up needing many
> thousands of divisions and it's not hard to construct inputs that take
> minutes to compute, although this is admittedly with ridiculously
> large inputs (~10^13), and AFAICS, the performance is OK with
>
On Sat, 4 Jan 2020 at 09:37, Dean Rasheed wrote:
>
> Well Vik has now provided a numeric implementation and it doesn't
> appear to be too much code.
>
BTW, I did a bit of research into the efficiency of Euclid's
algorithm. It's actually quite interesting:
It turns out that the worst case is when
On Thu, 2 Jan 2020 at 15:13, Tom Lane wrote:
>
> Stephen Frost writes:
> > * Dean Rasheed (dean.a.rash...@gmail.com) wrote:
> >> I'm not objecting to adding it, I'm just curious. In fact, I think
> >> that if we do add this, then we should probably add lcm() at the same
> >> time, since handling
Bonjour Vik,
Here is an updated patch fixing that.
As I said, welcome to arithmetic:-)
Patch v5 applies cleanly.
Doc: I'd consider using an example the result of which is 42 instead of
21, for obvious geek motivations. Possibly gcd(2142, 462) should be ok.
I got it wrong with my previou
On 04/01/2020 09:35, Fabien COELHO wrote:
>>> I'm unsure about gcd(INT_MIN, 0) should error. Possibly 0 would be
>>> nicer?
>>
>>
>> What justification for that do you have?
>
> ISTM that the current implementation has:
>
> \forall int4 n, n \neq MIN_INT4, \gcd(n, 0) = 0 ?
>
> In which case apply
Hello Tom,
Which architecture has single cycle division? I think it's way above
that, based on profiles I've seen. And Agner seems to back me up:
https://www.agner.org/optimize/instruction_tables.pdf
That lists a 32/64 idiv with a latency of ~26/~42-95 cycles, even on a
moder uarch like skylak
Bonjour Vik,
The point of swapping is to a void possibly expensive modulo, but this
should be done on absolute values, otherwise it may not achieve its
purpose as stated by the comment?
Ah, true. How widespread are these architectures that need this special
treatment? Is it really worth han
ex 57a1539506..e2b7d6d240 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -870,6 +870,32 @@
-43
+
+
+
+ gcd
+
+ gcd(a, b)
+
+ (same as argument types)
+ greatest common divisor
+ g
On 04/01/2020 01:26, Vik Fearing wrote:
> On 04/01/2020 01:21, Tom Lane wrote:
>> Vik Fearing writes:
>>> On 03/01/2020 20:14, Fabien COELHO wrote:
I'm unsure about gcd(INT_MIN, 0) should error. Possibly 0 would be nicer?
>>> What justification for that do you have?
>> Zero is the "correct" a
Vik Fearing writes:
> On 04/01/2020 01:21, Tom Lane wrote:
>> Zero is the "correct" answer for that, isn't it, independently of overflow
>> considerations?
> I would say not.
Oh, right, I was misremembering the identity gcd(a,0) as being 0 not a.
Never mind that then.
> The correct answer is
On 04/01/2020 01:21, Tom Lane wrote:
> Vik Fearing writes:
>> On 03/01/2020 20:14, Fabien COELHO wrote:
>>> I'm unsure about gcd(INT_MIN, 0) should error. Possibly 0 would be nicer?
>> What justification for that do you have?
> Zero is the "correct" answer for that, isn't it, independently of over
Vik Fearing writes:
> On 03/01/2020 20:14, Fabien COELHO wrote:
>> I'm unsure about gcd(INT_MIN, 0) should error. Possibly 0 would be nicer?
> What justification for that do you have?
Zero is the "correct" answer for that, isn't it, independently of overflow
considerations? We should strive to
On 04/01/2020 00:49, Tom Lane wrote:
> Vik Fearing writes:
>> On 03/01/2020 20:14, Fabien COELHO wrote:
>>> The point of swapping is to a void possibly expensive modulo, but this
>>> should be done on absolute values, otherwise it may not achieve its
>>> purpose as stated by the comment?
>> Ah, tr
Andres Freund writes:
> On 2020-01-03 18:49:18 -0500, Tom Lane wrote:
>> On a machine with single-cycle divide, it's likely that the extra
>> compare-and-branch is a net loss.
> Which architecture has single cycle division? I think it's way above
> that, based on profiles I've seen. And Agner see
Hi,
On 2020-01-03 18:49:18 -0500, Tom Lane wrote:
> On some older RISC architectures, integer division is really slow, like
> slower than floating-point. I'm not sure if that's true on any platform
> people still care about though. In recent years, CPU architects have been
> able to throw all th
Vik Fearing writes:
> On 03/01/2020 20:14, Fabien COELHO wrote:
>> The point of swapping is to a void possibly expensive modulo, but this
>> should be done on absolute values, otherwise it may not achieve its
>> purpose as stated by the comment?
> Ah, true. How widespread are these architectures
On 2020-01-03 18:00:01 -0500, Tom Lane wrote:
> Alvaro Herrera writes:
> > On 2020-Jan-03, Robert Haas wrote:
> >> Then every time we add a function, or anything else, we can bikeshed
> >> about whether it should go in pg_catalog or pg_extra!
>
> > Yeah, I was just thinking about that :-) I was
Alvaro Herrera writes:
> On 2020-Jan-03, Robert Haas wrote:
>> Then every time we add a function, or anything else, we can bikeshed
>> about whether it should go in pg_catalog or pg_extra!
> Yeah, I was just thinking about that :-) I was thinking that all
> standard-mandated functions, as well a
On 03/01/2020 20:14, Fabien COELHO wrote:
>
> Bonsoir Vik,
>
> +int4gcd_internal(int32 arg1, int32 arg2)
> +{
> + int32 swap;
> +
> + /*
> + * Put the greater value in arg1.
> + * This would happen automatically in the loop below, but
> avoids an
> + * ex
On 2020-Jan-03, Robert Haas wrote:
> On Fri, Jan 3, 2020 at 4:11 PM Alvaro Herrera
> wrote:
> > Maybe a very simple solution is indeed to have a separate pg_math or
> > pg_extra or whatever, which by default is *last* in the search_path.
> > That would make a user's gcd() be chosen preferently,
On Fri, Jan 3, 2020 at 4:11 PM Alvaro Herrera wrote:
> Maybe a very simple solution is indeed to have a separate pg_math or
> pg_extra or whatever, which by default is *last* in the search_path.
> That would make a user's gcd() be chosen preferently, if one exists.
Then every time we add a functi
On Fri, Jan 3, 2020 at 3:51 PM Merlin Moncure wrote:
> Is that right? Default search_path is for pg_catalog to resolve before
> public. Lightly testing with a hand rolled pg_advisory_lock
> implementation that raise a notice, my default database seemed to
> prefer the build in function. Maybe I'
On 1/3/20 4:10 PM, Alvaro Herrera wrote:
> Maybe a very simple solution is indeed to have a separate pg_math or
> pg_extra or whatever, which by default is *last* in the search_path.
> That would make a user's gcd() be chosen preferently, if one exists.
I'm liking the direction this is going.
Re
On 2020-Jan-03, Merlin Moncure wrote:
> On Fri, Jan 3, 2020 at 1:32 PM Robert Haas wrote:
> > True, but because of the way search_path is typically set, they'd
> > probably continue to get their own version anyway, so I'm not sure
> > what the problem is.
>
> Is that right? Default search_path
On 1/3/20 3:09 PM, Peter Eisentraut wrote:
> Geometry is generally in scope, though, for Postgres specifically and
> for databases in general.
>
> Abstract algebra is not in scope, so far, and we still haven't been told
> the use case for this.
It's funny, I think I've used gcd and lcm in real li
gt; > gcd() function that does anything other than take the greatest common
> > > divisor.
> >
> > As seen in this thread though, there can be edge cases of "take the
> > greatest common divisor" that might not be identically treated in a
> > thoroughly-review
On 2020-01-03 16:22, Tom Lane wrote:
Peter Eisentraut writes:
On 2020-01-02 15:50, Dean Rasheed wrote:
Out of curiosity, what was the original use-case for this?
Yeah, I'm wondering, is this useful for any typical analytics or
business application? Otherwise, abstract algebra functionality
less you've set up an unusual search_path
> > configuration, your own schemas probably precede pg_catalog in your
> > search path, besides which it seems unlikely that many people have a
> > gcd() function that does anything other than take the greatest common
> > divisor.
&g
schemas probably precede pg_catalog in your
> search path, besides which it seems unlikely that many people have a
> gcd() function that does anything other than take the greatest common
> divisor.
As seen in this thread though, there can be edge cases of "take the
greatest common divisor
Bonsoir Vik,
+int4gcd_internal(int32 arg1, int32 arg2)
+{
+ int32 swap;
+
+ /*
+* Put the greater value in arg1.
+* This would happen automatically in the loop below, but avoids an
+* expensive modulo simulation on some architectures.
+*/
ation, your own schemas probably precede pg_catalog in your
search path, besides which it seems unlikely that many people have a
gcd() function that does anything other than take the greatest common
divisor.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
On 1/3/20 1:46 PM, Robert Haas wrote:
> On Fri, Jan 3, 2020 at 1:10 PM Merlin Moncure wrote:
>> Just stop doing it. It's very little extra work to package an item
>> into an extension and this protects your hapless users who might have
>> implemented a function called gcd() that does something di
On Fri, Jan 3, 2020 at 1:10 PM Merlin Moncure wrote:
> Just stop doing it. It's very little extra work to package an item
> into an extension and this protects your hapless users who might have
> implemented a function called gcd() that does something different.
> Ideally, the public namespace sh
.
Patch attached.
--
Vik Fearing
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 57a1539506..e2b7d6d240 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -870,6 +870,32 @@
-43
+
+
+
+
On Fri, Jan 3, 2020 at 10:24 AM Robert Haas wrote:
>
> On Fri, Jan 3, 2020 at 10:23 AM Tom Lane wrote:
> > Now, those functions were just exposing libc functionality, so there
> > wasn't a lot of code to write. There might be a good argument that
> > gcd isn't useful enough to justify the amount
On 2020-Jan-03, Robert Haas wrote:
> On Fri, Jan 3, 2020 at 10:23 AM Tom Lane wrote:
> > Now, those functions were just exposing libc functionality, so there
> > wasn't a lot of code to write. There might be a good argument that
> > gcd isn't useful enough to justify the amount of code we'd have
On Fri, Jan 3, 2020 at 10:23 AM Tom Lane wrote:
> Now, those functions were just exposing libc functionality, so there
> wasn't a lot of code to write. There might be a good argument that
> gcd isn't useful enough to justify the amount of code we'd have to
> add (especially if we allow it to scop
Peter Eisentraut writes:
> On 2020-01-02 15:50, Dean Rasheed wrote:
>> Out of curiosity, what was the original use-case for this?
> Yeah, I'm wondering, is this useful for any typical analytics or
> business application? Otherwise, abstract algebra functionality seems a
> bit out of scope.
No
On 2020-01-02 15:50, Dean Rasheed wrote:
Out of curiosity, what was the original use-case for this?
Yeah, I'm wondering, is this useful for any typical analytics or
business application? Otherwise, abstract algebra functionality seems a
bit out of scope.
--
Peter Eisentraut ht
Normally gcd() returns a positive integer, and gcd(a,0) = gcd(a,a) =
abs(a). But since abs(INT_MIN) cannot be represented as a 32-bit
integer, both those cases should throw an integer-out-of-range error.
I'm also in favor of that option, rather than sending a negative result as
a result.
A
On Sat, Dec 28, 2019 at 12:15 PM Fabien COELHO wrote:
>
>
> 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.
Proliferation of code in the public namespace; it can displace code
that is written
Stephen Frost writes:
> * Dean Rasheed (dean.a.rash...@gmail.com) wrote:
>> I'm not objecting to adding it, I'm just curious. In fact, I think
>> that if we do add this, then we should probably add lcm() at the same
>> time, since handling its overflow cases is sufficiently non-trivial to
>> justi
Greetings,
* Dean Rasheed (dean.a.rash...@gmail.com) wrote:
> I'm not objecting to adding it, I'm just curious. In fact, I think
> that if we do add this, then we should probably add lcm() at the same
> time, since handling its overflow cases is sufficiently non-trivial to
> justify not requiring
Out of curiosity, what was the original use-case for this?
I'm not objecting to adding it, I'm just curious. In fact, I think
that if we do add this, then we should probably add lcm() at the same
time, since handling its overflow cases is sufficiently non-trivial to
justify not requiring users to
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 befor
On 12/29/19 02:30, Fabien COELHO wrote:
>>> 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...
> ...
> Because I do not trust C modulo as I had a lot of problems with it? :-)
If I recall correct
ap added.
Thanks!
--
Vik
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 57a1539506..b2c663cd92 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -870,6 +870,19 @@
-43
+
+
+
+ gcd
+
+gcd(a, b)
+
+ (same as argumen
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?
gcd(b, a)).
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index 57a1539506..b2c663cd92 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -870,6 +870,19 @@
-43
+
+
+
+ gcd
+
+
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
-43
+
+
+
+ gcd
+
+gcd(a, b)
+
+ (same as argument types)
+ greatest common divisor
+ gcd(1071, 462)
+ 21
+
+
diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c
index 04825fc77d..bc74d367bb 100644
---
70 matches
Mail list logo
