Message362098
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". |
|
Date |
User |
Action |
Args |
2020-02-16 20:04:47 | Dennis Sweeney | set | recipients:
+ Dennis Sweeney, tim.peters, rhettinger, mark.dickinson, steven.daprano, SilentGhost, serhiy.storchaka, Ananthakrishnan |
2020-02-16 20:04:47 | Dennis Sweeney | set | messageid: <1581883487.36.0.493268508164.issue39648@roundup.psfhosted.org> |
2020-02-16 20:04:47 | Dennis Sweeney | link | issue39648 messages |
2020-02-16 20:04:47 | Dennis Sweeney | create | |
|