str(bigint) is slow

[David Eppstein]

In article <tm1ve0pn6l3c3ifi85amlkdb11itfad3rd at 4ax.com>,
 Tim Roberts <timr at probo.com> wrote:

> Bryan <belred1 at yahoo.com> wrote:
> >
> >does anyone know how to make this faster?  it seems that str(x) is the slow 
> >part.
> 
> Do you understand how much arithmetic is required to do this?  You're
> talking about more than 400,000 division/modulo operations on a multi-byte
> number that is 166,000 bytes long.  I, for one, am not surprised that it
> takes a long time.

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?

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