str(bigint) is slow
eppstein at ics.uci.edu
Sat Jul 10 17:48:30 CEST 2004
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
More information about the Python-list