Home Original page

str(bigint) is slow

Tim Peters tim.peters at gmail.com
Sat Jul 10 03:11:32 EDT 2004 
[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.
More information about the Python-list mailing list