Horton

Re: Greatest Common Divisor

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Vik Fearing <vik.fearing@2ndquadrant.com>, Fabien COELHO <coelho@cri.ensmp.fr>, Stephen Frost <sfrost@snowman.net>, Dean Rasheed <dean.a.rasheed@gmail.com>, Chapman Flack <chap@anastigmatix.net>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2020-01-04T00:10:01Z
Lists: pgsql-hackers 
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 the transistors they needed at such problems.  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 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 skylake-x.

Greetings,

Andres Freund

Commits

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