str(bigint) is slow

[David Eppstein]

In article <mailman.199.1089443500.5135.python-list at python.org>,
 Tim Peters <tim.peters at gmail.com> wrote:

> [David Eppstein]
> > It doesn't have to be that slow -- you could do a single div/mod by
> > 10**(n/2) (n=#digits of input) to split it into two numbers of roughly
> > half the number of digits, and continue recursively in both halves.  The
> > bottleneck would be the first div/mod -- Python currently uses Karatsuba
> > for that, right?
> 
> Computing the power in a decimal-friendly base to begin with runs much
> faster than that (and I posted code the last time this came up, a
> couple of weeks ago).
> 
> Python uses Karatsuba for multiplication, not division.  Karatsuba may
> or may not trigger during the computation of 10**(n/2) (depending on
> how large n is), but never triggers during division.

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.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science