Author Dennis Sweeney
Recipients Ananthakrishnan, Dennis Sweeney, SilentGhost, mark.dickinson, rhettinger, serhiy.storchaka, steven.daprano, tim.peters
Date 2020-02-16.20:04:47
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1581883487.36.0.493268508164.issue39648@roundup.psfhosted.org>
In-reply-to
Content
I think the behavior of gcd() == 0 is correct, but it should be documented, because it isn't completely obvious.

Arguments for gcd() == 0:

- Preserves the invariant gcd(itertools.chain(iterables)) == gcd(itertools.starmap(gcd, iterables)) in the case that some iterables are empty.

- Return a "neutral element" (not technically true for negative integers because gcd(0, a) == abs(a) != a, but it does get "ignored")

Other considerations:

- The "common divisors" of the empty set are the integers d such that for all x in the empty set, d divides x, which is to say, all of the integers. Then there is no greatest of these common divisors. The same is true if we try gcd(0, 0, ... 0).

- The above is only fixed if we interpret "greatest" in the sense of divisibility, where 0 > everything because everything divides 0. In particular, we can say that g is a greatest common divisor of a_1, ..., a_n if g | a_i for all i, and for any d with d | a_i for all i, we also have d | g. Using this definition also requires that we specify that if there are two gcds, we return the positive one.
I believe this is the correct interpretation, but it may not be obvious, since it assumes that proof that such a number even exists.

- Another common definition of the greatest common divisor of {a_1, ..., a_n} is the smallest positive integer expressible as an integer linear combination x_1 a_1 + ... + x_1 a_2, where x_i are integers. But this definition breaks on gcd(), gcd(0), gcd(0, 0), etc, since no positive integers are expressible.

In short, while I agree with the behavior, I think there should be a clarifying sentence in the docs saying "returns 0 if all of the arguments are 0".
History
Date User Action Args
2020-02-16 20:04:47Dennis Sweeneysetrecipients: + Dennis Sweeney, tim.peters, rhettinger, mark.dickinson, steven.daprano, SilentGhost, serhiy.storchaka, Ananthakrishnan
2020-02-16 20:04:47Dennis Sweeneysetmessageid: <1581883487.36.0.493268508164.issue39648@roundup.psfhosted.org>
2020-02-16 20:04:47Dennis Sweeneylinkissue39648 messages
2020-02-16 20:04:47Dennis Sweeneycreate