Re: Greatest Common Divisor

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 life way more often
than sinh and cosh, maybe even as often as sin and cos. For example,
how many times around will I have to go with this engine crankshaft
to be able to confirm the painted links on the timing chain really
do line up with the sprocket marks? (Need to count the sprocket
teeth and the chain links.)

Or, if I'm cycling through two different-length tuple stores, how
many times before the same tuples coincide again? That isn't a question
I've yet had an occasion to face, but I don't have to squint real hard
to imagine it arising in a database in some situation or other. This
is just me riffing, as of course I'm not the person who had such a
pressing use case as to justify sitting down to write the patch.

Another funny thing: this message sent me googling just to indulge
my own "is gcd more abstract algebra or number theory?" quibble*, and
I ended up discovering there are more algorithms for it than the
Euclidean one I remember.

There's a binary one using only ands, subtractions, and shifts,
asymptotically the same as Euclid but perhaps somewhat faster:
https://en.wikipedia.org/wiki/Binary_GCD_algorithm

It looks fairly simple to code up, if not quite as short as Euclid.

There's at least one specific to representations like numeric:
https://en.wikipedia.org/wiki/Lehmer%27s_GCD_algorithm

... considerably more effort to implement though.

It might be possible, if there are crypto libraries we're already
linking to for other reasons like SSL, there could be good
big-number gcd implementations already in there.

Regards,
-Chap


* maybe I've decided to call it number theory if the things being gcd'd
are integers, abstract algebra if they belong to other commutative rings.