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: Andres Freund <andres@anarazel.de>
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:17:50Z
Lists: pgsql-hackers 
Andres Freund <andres@anarazel.de> 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 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.

Huh.  I figured Intel would have thrown sufficient transistors at that
problem by now.  But per that result, it's worth having the swap step
even on CISC, never mind RISC.

			regards, tom lane

Commits

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