GCD and the magic of subtraction

Re:GCD and the magic of subtraction by jjtheblunt on Tuesday August 25, 2020 @01:22AM (#24268327)

It's not necessary that the set of numbers be coprime: {2,4} fed into Euclid's algorithm would proceed to reduce to {2,2} then {2,0} then yield {2}.

In general Euclid's algorithm is a special case of Buchberger's algorithm, q.v., if interested.

[ Parent | on HN ]

Re:GCD and the magic of subtraction by plumsempy on Tuesday August 25, 2020 @02:16AM (#24268553)

It is definitely not necessary. Because the gcd of 2 and 4 is 2, thus we have 2(1) and 2(2). 2 and 1 are coprime and thus will reduce down to 1, the common part left out is 2 and the uncommon part is 1, as always 1.

Thanks about the Buchberger intro I didn't know about that.

[ Parent | on HN ]

Re:GCD and the magic of subtraction by bollu on Tuesday August 25, 2020 @02:04AM (#24268483)

What's q.v?

Also, Buchberger is a special case of Knuth-Bendix completion :D

[ Parent | on HN ]

Re:GCD and the magic of subtraction by JadeNB on Tuesday August 25, 2020 @02:52AM (#24268721)

> What's q.v?

"quod vide" = "which see": https://en.wiktionary.org/wiki/quod_vide .

[ Parent | on HN ]

Re:GCD and the magic of subtraction by m12k on Tuesday August 25, 2020 @09:30AM (#24271106)

So basically "see also" in Latin?

[ Parent | on HN ]

Re:GCD and the magic of subtraction by jjtheblunt on Tuesday August 25, 2020 @09:35AM (#24271145)

good point: "see" even by itself works, but i had lots of Latin so didn't think of it.

[ Parent | on HN ]

Re:GCD and the magic of subtraction by jjtheblunt on Tuesday August 25, 2020 @03:12AM (#24268824)

yep...fun stuff.

https://www.amazon.com/Ideals-Varieties-Algorithms-Computati...

covers much of this topic

[ Parent | on HN ]