Horton

Re: Greatest Common Divisor

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Stephen Frost <sfrost@snowman.net>, Vik Fearing <vik.fearing@2ndquadrant.com>, Fabien COELHO <coelho@cri.ensmp.fr>, Chapman Flack <chap@anastigmatix.net>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2020-01-04T17:01:48Z
Lists: pgsql-hackers 
Dean Rasheed <dean.a.rasheed@gmail.com> 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^130000), and AFAICS, the performance is OK with
> "normal" sized inputs. Should we put a limit on the size of the
> inputs?

No, but a CHECK_FOR_INTERRUPTS in the loop would be well-advised,
if there's not one already inside the called functions.

> There are apparently more efficient algorithms, but I think that
> should definitely be kept out of scope for this patch.

+1

			regards, tom lane

Commits

  1. Add functions gcd() and lcm() for integer and numeric types.