> rely on having an FFT-based fast multiplication algorithm, together with
> some form of divide-and-conquer division---is this right?

Yes, that's true: fast str() relies on fast division.  I had assumed Python already had fast division; if it doesn't, I'd consider that a bug, too.

> What's your use-case for printing huge integers fast?

Note that it's not a question of printing them *fast*.  With a quadratic time algorithm, it's infeasible to print huge numbers *at all*.  My personal use case is doing computations in Thompson's group F; an element of F is a list of humongous fractions.  But I expect it's a problem that often comes up in mathematical programming.  I'll admit it isn't a very important bug, since anyone who is harmed by it will either use a different language, or use gmpy, or print in hex.  But it's still a bug.

> Regarding GMP, I believe there are licensing issues:  it's not legal to
> include GMP in core Python and release Python under its current non-GPL
> license, or something like that---I don't know anything about the details.

I don't see what the problem would be.  Python's LICENSE file says that Python's license is GPL compatible.  And in any case, GMP is LGPL, not GPL, so any program can link to it.