str(bigint) is slow

[Bryan]

tim,

your code is incredibly fast... thank you

bryan


Tim Peters 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.