GCD in standard library?

Gareth McCaughan Gareth.McCaughan at pobox.com
Thu Mar 13 09:33:30 CET 2003

Tim Peters wrote:

> [Blake Garretson]
> > If Python comes with "batteries included", where's GCD?
> httplib and builtin unbounded ints are batteries; gcd is a throwaway finger
> exercise in a Usenet posting.  BTW, I've never seen another user community
> so keen to lobby for inclusion of every 1-, 2- and 3-line function they can
> dream up.  Even Common Lisp had the good grace to restrict itself to
> 12-liners, like builtin Roman numeral output <wink>.

Common Lisp *has* a GCD function. And an LCM. It inexplicably
lacks Euler's phi function <0.8 wink>.

Providing a GCD function isn't obviously mad, but what
would be more useful is the "extended GCD" function that
finds not only d = gcd(a,b) but also m,n such that ma+nb=d.
This is a bit less of a "finger exercise" than plain GCD,
and is useful slightly more often than you might think.
(I needed one myself recently for a hairy numerical
simulation in C++. Not that having it in Python would
have saved me any time there. :-) )

For what it's worth, I'm all in favour of an enormous
standard library provided that

  - it's really well designed
  - it's efficiently, portably and robustly implemented
  - all of it is actively maintained and can be relied on
    remaining so for a good while

None of that comes for free. But *if* it were guaranteed
for, say, a Python number theory library then I don't see
any reason not to include it with Python. I suspect that
anyone with the necessary skills and time would do more
good by helping to provide a good Rational type.

Gareth McCaughan  Gareth.McCaughan at pobox.com
.sig under construc

More information about the Python-list mailing list