str(bigint) is slow

[Tim Peters]

[David Eppstein]
> I wonder what the breakpoint would be for doing divisions by Newton
> iteration with Karatsuba multiplication (asymptotic complexity = same as
> multiplication) vs naive long division.  Probably too many digits to
> make it worthwhile most of the time.

GNU's GMP developers spend their lives finding these tradeoffs, so
read the GMP docs and mailing lists for more than you can likely bear
on this,

Python's bigint implementation is aimed at 100% portability and
correctness more than speed.  GMP doesn't hesitate to drop into
hyper-optimized hand-coded assembler when it helps.  Partly as a
consequence of the resulting speed difference in the lowest-level
primitives, the cutoff for plain Karatsuba multiplication in Python is
so high that Karatsuba rarely triggers in Python (and probably never
in 99.99% of Python applications).

Do look at the last, recent iteration of this topic.  The asymptotics
of elementary arithmetic operations are independent of base, so
computing powers in a decimal-friendly base to begin with wins big by
allowing conversion to decimal string to be done in time linear in the
number of digits.  This allowed a pure-Python program to run circles
around GMP in producing the decimal representation of a very large
power.